[프로그래머스] 입국심사(Python)

1. 아이디어

심사관의 입장에서 문제를 바라보자. "주어진 시간"동안 심사관 1명당 처리할 수 있는 입국자 수를 구한다.

여기서, "주어진 시간"은 어떻게 찾을까?? 우선 제한사항에 따르면, 심사관이 입국자를 심사하는데 최소 1분이 걸리기 때문에, 최소값은 1이다. 그리고 모든 입국자가 심사가 가장 오래걸리는 심사관에게만 심사를 받으면 최대값은 max(times) x n이다. 따라서 주어진 시간은 1 ~ max(times) x n의 범위에 존재하며, 이 범위 안에서, 우리는 모든 입국자가 심사를 받는데 걸리는 최소 시간을 구하면된다.

주어진 시간동안 심사관 1명당 처리할 수 있는 입국자 수를 구한 결과를 모두 더하여 n보다 크거나 같으면, 모든 입국자가 해당 시간안에 심사를 받을 수 있다. 다만, 그 시간이 최소값을 의미하는 것은 아니기 때문에, 탐색을 계속 진행해야한다.

2. 코드

def solution(n, times):
    times.sort() # 선형시간안에 최대 값을 찾을 수 있음
    max_consume = times[-1] * n
    left, right = 1, max_consume
    answer = 0

    while left <= right:
        mid = (left+right) // 2
        x = 0
        for i in range(len(times)): 
            x += mid // times[i]
            if x == n: break # 생략가능

        if x < n: left = mid + 1
        elif x >= n:
            answer = mid
            right = mid - 1

    return answer