[Python] 입국심사

문제 참고

프로그래머스

 

코드 작성

def solution(n, times):
    answer = 0
    min_value = -1
    def binary_search(start, end, n, times, min_value):
        while start <= end:
            count = 0
            mid = (start + end) // 2
            for time in times:
                count += (mid // time)
            if count >= n:
                if min_value == -1:
                    min_value = mid
                else:
                    min_value = min(min_value, mid)
                end = mid - 1
            else:
                start = mid + 1
        return min_value
    
    times.sort()
    end = times[-1] * n
    answer = binary_search(0, end, n, times, min_value)
    return answer

 

이분 탐색 알고리즘을 이용한다.

끝나는 시간은 모두가 가장 긴 시간 동안 상담을 받는 경우이므로, end = times[-1] * n 이다.

상담하는 시간이 지날 때마다 바로 다음 사람이 상담을 받을 수 있기 때문에 count 변수를 만들어 mid//time 값을 더해준다.

그러면 mid라는 시간동안 상담받을 수 있는 사람의 수 count가 집계된다.

만약 count가 n보다 크다면 end 값을 mid보다 작게 만들고, n보다 작다면 start를 mid보다 크게 만든다.