1. 문제 설명

입국심사

2. 문제 분석

• 처음에는 힙을 사용했다. 사람 수만큼 루프를 돌리면서 심사관 목록 중 가장 빨리 끝나는 시간을 return하고 한 번 심사를 마친 뒤에는 초깃값을 offset으로 더해주면서 다시 push해주었다. 하지만 문제에서 요구하는 n의 크기와 times의 범위가 매우 컸기 때문에, 범위가 커질 수록 시간 초과가 걸렸다.

'이분 탐색'을 통해 사람 n명을 심사하는 데 걸리는 가장 짧은 최적의 시간을 구한다. 만일 그 시간 동안 모든 사람을 검사할 수 있다면 좀 더 시간을 타이트하게 잡고, 그렇지 않다면 좀 느슨하게 잡자.

1. 사람들을 심사하는 데 걸리는 최댓값은 "가장 많은 시간을 쓰는" 심사관이 모든 사람들 n명을 심사한 경우이다.
2. 이분 탐색을 통해 mid를 정하자.
3. mid 동안 모든 심사관이 총 n명을 확인할 수 있는지 검사한다. 이때 각 심사관이 mid 시간 동안 검사할 수 있는 사람 수는 (mid // time)이다.
4. 최소 mid 값을 찾아 return한다.

3. 나의 풀이

def solution(n, times):
    result = 0
    times.sort()
    left, right = 0, times[-1]*n
    # n명을 검사하는 데 걸리는 최소 시간 -> mid를 통해 "최소 시간" 찾기
    while left <= right:
        # 주어진 최소 mid를 찾아 result로 넘길 때까지 이분 탐색
        mid = (left + right) // 2
        check = 0
        checkable = False
        # mid는 각 심사관이 사용할 수 있는 시간
        for time in times:
            check += mid // time
            if check >= n: 
                checkable = True
                break
        if checkable:
            # mid분으로 n명 검사 가능
            result = mid
            right = mid - 1
        else:
            left = mid + 1
    return result