Level 3 → 이분 탐색
문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
입출력 예
| n |
times |
return |
| 6 |
[7, 10] |
28 |
나의 Solution <Python>
def solution(n, times):
answer = 0
times.sort()
low = 1 # 최소 시간 → 1분
high = int(times[len(times) - 1] * n) # n명의 사람이 입국 심사하는 데 걸리는 최대 시간 → 60분
while low < high:
ppl = 0 # mid분 동안 입국 심사 완료한 사람의 수
mid = int((low + high) / 2) # 모든 사람 입국 심사 소요 시간
for i in range(len(times)):
ppl += int (mid / times[i]) # mid분 동안 i번째 gate 입국 심사 가능한 사람 수
if ppl >= n: # n명보다 많이 입국 심사 통과
high = mid # decrease mid
else: # n명 통과X (less than n)
low = mid + 1 # increase mid
answer = high
return answer
low, mid, high => 입국 심사에 소요된 총 시간
디버깅
n = 6명의 사람들
times = 입국 심사대(소요 시간)
low = 1
high = (2 - 1) * 6 = 60
while 1 < 60:
(low = 1, high = 60)
mid = (1 + 60) / 2 = 30
ppl = (30 / 7) + (30 / 10) = 7
7 >= 6 → high = 30
while 1 < 30:
(low = 1, high = 30)
mid = (1 + 30) / 2 = 15
ppl = (15 / 7) + (15 / 10) = 3
3 < 6 → low = 15 + 1 = 16
while 16 < 30:
(low = 16, high = 30)
mid = (16 + 30) / 2 = 23
ppl = (23 / 7) + (23 / 10) = 5
5 < 6 → low = 23 + 1 = 24
while 24 < 30:
(low = 24, high = 30)
mid = (24 + 30) / 2 = 27
ppl = (27 / 7) + (27 / 10) = 5
5 < 6 → low = 27 + 1 = 28
while 28 < 30:
(low = 28, high = 30)
mid = (28 + 30) / 2 = 29
ppl = (29 / 7) + (29 / 10) = 6
6 >= 6 → high = 29
while 28 < 29:
(low = 28, high = 29)
mid = (28 + 29) / 2 = 28
ppl = (28 / 7) + (28 / 10) = 6
6 >= 6 → high = 28
while 28 == 28: break
answer = 28 (high)
