[python 이분 탐색] 입국심사 프로그래머스

이분탐색은 원하는 값이 중간값보다 크다면 오른쪽을 탐색하고 중간값보다 작다면 왼쪽을 탐색하며 원하는 값을 탐색하는 기법입니다.

 

예를 들어, 1~10까지 상대가 생각한 수를 이분탐색 기법을 사용하여 찾아보겠습니다. 상대가 생각하는 수를 7이라고 생각해봅니다.

 

중간값 < 원하는 값 up

중간값 > 원하는 값 down

 

1. 1~10의 중간 값 = 5 -> up

2. 6~10의 중간 값 = 8 -> down

3. 6~8 의 중간 값 = 7 -> 답

 

입국심사 문제는 입국 심사하는데 걸리는 시간을 최소화하도록 입국 심사 하는 사람들을 심사대에 잘 배분하는 것입니다. 심사하는데 걸리는 시간을 각 심사대가 처리하는 시간으로 나눈 몫을 더하면 입국 심사 하는 사람들의 수가 나옵니다. 이 점을 활용하여 이분 탐색을 실시합니다. 

솔루션

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

        if m >= n:
            right = mid
        else:
            left = mid+1

    return left

left를 반환하는 이유는 입국 심사하는데 걸리는 최소한의 시간을 반환해야 하기 때문입니다.