[알고리즘] 입국심사 (Python)

문제보기

풀이

이 문제의 핵심은 모든 사람이 심사를 받는데 걸리는 시간 즉 return 해야하는 값을 기준으로 이분 탑색을 하는 것 이다.

이분 탐색의 범위는 times배열의 최솟값 부터 최댓값 * n이 될 것이다.

이분 탐색의 기준은 해당 시간 즉 mid값 동안 입국심사를 마친 사람의 수와 n값을 비교해야 한다.

• mid시간동안 심사를 마친 사람의 수가 n보다 클 경우 범위를 줄인다. (right = mid)
• mid시간동안 심사를 마친 사람의 수가 n보다 작을 경우 범위를 늘린다. (left = mid+1)

여기서 중요한 점은 mid시간동안 심사를 마친 사람의 수가 n과 같을 경우 범위를 줄여(right = mid) 최소값을 찾을 수 있게 한다.

코드

def solution(n, times):
    left, right = min(times), max(times)*n
    
    while left < right:
        mid = (left+right) // 2
        
        total = 0
        for time in times:
            total += mid // time
        
        if n <= total:
            right = mid
        else:
            left = mid+1
            
    return left