2022.04.19 [프로그래머스] (python 파이썬) 입국심사

 

https://programmers.co.kr/learn/courses/30/lessons/43238

코딩테스트 연습 - 입국심사

 

---

풀이

이 문제는 모든 상황을 for문으로 확인하기에는 범위가 너무 커서 이분탐색을 이용해 문제를 해결하였다.

이분탐색을 이용하기위해 start, end를 설정하였다. start는 걸리는 시간의 최소값, end는 걸리는 시간의 최대값으로 설정하였다. 

이후, while문을 이용하여 이분탐색을 사용했다. 

for문을 이용하여 mid의 시간일 때, 모든 심사관이 검사할 수 있는 사람의 수를 cnt에 저장한 후, n과 비교하여 같으면 end값을 mid-1로 설정해주었다. 이유는 만약 n과 cnt이 6이라도 mid가 29이면 29보다 작은 값인 28도 cnt이 6이 되기 때문에 더 작은 값을 검사하기 위해서 이다.

cnt이 n보다 크면 시간을 줄여 심사관이 검사할 수 있는 사람의 수를 줄여야 하기 때문에 end를 mid-1로 설정한다.

cnt이 n보다 작으면 시간을 늘려야 하기 때문에 start를 mid+1로 설정한다.

이후 while문이 종료되면 start값과 end값이 같아진다. 이 값이 가장 적절한 값이기 때문에 answer에 대입해준다.

 

아래의 그림을 보면 보다 쉽게 이해할 수 있다.

출처 : https://happy-obok.tistory.com/10?category=526383

출처 : https://happy-obok.tistory.com/10?category=526383

def solution(n, times):
    answer = 0
    start=0
    end=max(times)*n
    while start<=end:
        mid=(start+end)//2
        cnt=0
        for i in times:
            cnt+=mid//i
        if n==cnt:
            end=mid-1
        elif cnt>n:
            end=mid-1
        else:
            start=mid+1
    answer=start
    return answer