유형

  • 이진 탐색 (Binaray Search)

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

제한사항

  • 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
  • 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
  • 심사관은 1명 이상 100,000명 이하입니다.

이진 탐색 INSIGHT

  • LEFT의 의미 → 최소, 하한선, 최적값
  • RIGHT의 의미 → 최대, 상한선, 최악값
  • MID의 의미 → 적당한 값, 정답 후보 ((left + right)//2)
  • 이진 탐색의 종료 지점은
    • (MID == ANSWER) 이거나
    • (LEFT > RIGHT) 인 지점 (더 이상 분할이 불가능한 지점)

우선 이 문제의 입력의 수가 10억까지 나올 수 있다는 점에서 $O(logN)$ 알고리즘을 떠올려야 한다.

만약 이진 탐색으로 풀려고 한다면, LEFT, RIGHT, MID를 정의해야 한다.

이 문제에서는 ‘심사 받는데 걸리는 최소 시간’을 구하는 것이므로 MID가 시간이 되야한다.

알고리즘 유도

  1. 가장 시간이 오래 걸리는 경우 → 가장 오래 걸리는 심사대만 이용했을 경우 (max(times) * n)
  2. (주어진 시간) $\div$ (심사하는데 걸리는 시간) → 주어진 시간 동안 한 심사대에서 최대한 처리할 수 있는 수
    1. i번째 심사대의 최대 수용 인원을 $\alpha_i$로 정의한다.
  3. $\sum_{i=1}^{k}\alpha_{i} =$ 주어진 시간 동안 1부터 $k$번째 심사대까지 골구루 이용했을 때 최대 수용 인원
  4. 심사대 몇 개를 이용하던간에, 어떠한 방법으로든 주어진 시간 동안 모두 처리할 수 있다면 OK
  5. left > right인 지점까지 구하면서 최소의 시간을 구한다.
    1. 주어진 시간 동안 수용할 수 있는 인원이 충분할 경우 더 적은 시간을 할당하고
    2. 인원이 충분하지 않을 경우 더 많은 시간을 할당한다.

알고리즘 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
def solution(n, times):
    left = 1
    right = max(times) * n
    answer = 0
    
    while left <= right:
        mid = (left + right) // 2
        alpha = 0
        for time in times:
            alpha += mid // time
            if alpha >= n: 
                break # k번째 심사대까지의 수용 인원의 합이 심사 대상보다 많은 경우 break
        if alpha >= n:
            answer = mid # 시간이 충분할 경우 정답 후보
            right = mid - 1
        else:
            left = mid + 1
            
    return answer