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

1. 입국심사

1.1. 문제유형

• 이분탐색

1.2. 자료구조

• times (list): 심판관별 심사시간
• left, right (int): 최소 시간, 최대 시간
• mid (int): 정답으로 지정한 left, right의 중간값
• cnt (int): mid 시간안에 완료한 승객 수

1.3. 해결과정

1. 구하고자 하는 것은 최소 시간이다.
2. 이분탐색을 사용하여 정답 시간을 설정 후 지정한 시간안에 완료되는 지를 구한다.
3. left, right 지정 후 left <= right일 동안 다음 과정을 반복한다.
4. mid = (left+right)//2 중간값 지정 후, mid 시간안에 몇 명이 완료될 수 있는 지 계산한다.
5. cnt는 mid 시간을 times 별로 나눈 몫을 더한 값이다.

def solution(n, times):
    answer = 0
    left, right = 0, min(times)*n

    while left<=right:
        mid = (left+right)//2
        cnt = 0
        for t in times:
            cnt += mid//t
        if cnt < n:
            left = mid+1
        else:
            right = mid-1
            answer = mid
    return answer