프로그래머스: 입국심사

문제

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

 

문제 풀이

 n명이 입국심사를 하는데 심사대에 따라 걸리는 시간을 반환하는 문제이다. 이때 심사 대마다 걸리는 시간은 각기 다르다. 이 문제는 분류와 같이 `이분 탐색`으로 풀어야 시간 내에 통과가 가능하다. 즉, `모두 입국하는데 걸리는 시간 // 각 심사대별 심사시간 = 입국자 수`를 만족하는 지를 찾아야 하기 때문에 `이분 탐색`으로 문제를 풀어야 한다.

 

 `이분 탐색`에서는 `left`, `right`를 설정하여야 하는데 이는 가장 짧게 걸리는 시간 1과, 모든 입국자들이 가장 큰 심사대를 통과하는 경우 `입국자 수 * max(times)`로 설정하면 된다.

 

코드

def solution(n, times):
    answer = 0

    length = len(times)
    left = 1
    right = (length + 1) * max(times)

    while left <= right:
        mid = (left + right) // 2

        cnt = 0
        for time in times:
            cnt += mid // time

        if cnt >= n:
            answer = mid
            right = mid - 1
        else:
            left = mid + 1

    return answer