입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때,모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return
제한사항
입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하
심사관은 1명 이상 100,000명 이하
"""
입출력 예시)
n = 6, times = [7, 10] -> 28
"""
# n = 6, times = [7, 10] -> 28
# 가장 첫 두 사람은 바로 심사를 받으러 감
# 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받음
# 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받음
# 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받음
# 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고
# 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝남
# 입출력 예시 해석
(입국심사대)
t1 t2
-----------------
(시간) 사람(/끝나는 시간)
n1(/7) n2(/10)
7 n3(/14)
10 n4(/20)
14 n5(/21)
20 | | <- (n6이 t2로 간다면 시작 시간은 20분으로 더 빠르지만, 끝나는 시간이 30분이 됨)
+ 1 n6(/28)
=> 최소 시간: 28분
6번째 사람이 1분 더 기다려서 첫 번째 심사대에 간 이유
두 번째 심사대(10분)로 간다면 시작 시간은 20분으로 더 빠르지만 끝나는 시간이 30분 (20 + 10)
1분 더 기다려서 첫 번째 심사대(7분)로 간다면 시작 시간은 21분이지만, 끝나는 시간이 28분 (21 + 7)
=> 1분 더 기다려서 첫 번째 심사대에서 심사를 받는 것이 총 심사 시간이 더 빠름
## 의사 코드 ##
# 탐색 범위가 100만 이상 -> 이분탐색
# 모든 사람이 심사를 받는데 걸리는 시간을 최소화하려면 시간이 적게 걸리는 심사대에서 최대한 많은 심사를 진행해야 함
# 심사에 걸리는 시간을 이분탐색
# 1) left = 1, right = 가장 오래 걸리는 최악의 심사 시간 -> max(times) * n
# 2) 현재 탐색하는 시간(mid)동안 심사가 가능한지 판단
# mid = (left + rigth) // 2
# 3) <현재 심사 가능한 인원수> 구하기
# for time in times:
# total += mid // time
# 4) <현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 많으면 현재 탐색한 시간(mid)보다 아래에서 다시 찾음
# -> 시간을 너무 여유있게 잡았기 때문에 심사에 걸리는 시간을 줄이기
# 5) <현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 적으면 현재 탐색한 시간(mid)보다 위에서 다시 찾음
# -> 시간을 너무 짧게 잡았기 때문에 심사에 걸리는 시간 늘리기
통과한 코드
def solution(n, times):
# left: 최소 시간 = 1분
# right: 최악의 시간 = max(times) * n
left, right = 1, max(times) * n
while left <= right:
# 현재 탐색하는 시간
mid = (left + right) // 2
# 현재 심사 가능한 인원수
total = 0
for time in times:
# 현재 심사 가능한 인원수 => 모든 심사관이 mid분 동안 심사한 사람의 수
total += mid // time
# 모든 심사관을 거치지 않아도 mid분 동안 n명 이상 심사할 수 있다면 break
if total >= n:
break
# <현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 같거나 많으면 현재 탐색한 시간(mid)보다 아래에서 다시 탐색
if total >= n:
right = mid - 1
# <현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 적으면 현재 탐색한 시간(mid)보다 위에서 다시 탐색
elif total < n:
left = mid + 1
return left
탐색 범위
left(최소 시간)
mid(중간값)
right(최대 시간 => 최악의 경우)
현재 심사 가능한 인원수(total)와 심사해야 하는 인원수(n)을 비교해서 탐색 범위 조정
과정 확인
n = 6
times = [7, 10]
"""
left: 1, right: 60
현재 탐색하는 시간(mid): 30
time: 7, 현재 total: 이전 total (0) + mid // time (4) = 4
time: 10, 현재 total: 이전 total (4) + mid // time (3) = 7
현재 심사 가능한 최종 인원수(total): 7
<현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 같거나 많은 경우
갱신된 right: (mid - 1) = 29
------------------------------
left: 1, right: 29
현재 탐색하는 시간(mid): 15
time: 7, 현재 total: 이전 total (0) + mid // time (2) = 2
time: 10, 현재 total: 이전 total (2) + mid // time (1) = 3
현재 심사 가능한 최종 인원수(total): 3
<현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 적은 경우
갱신된 left: (mid + 1) = 16
------------------------------
left: 16, right: 29
현재 탐색하는 시간(mid): 22
time: 7, 현재 total: 이전 total (0) + mid // time (3) = 3
time: 10, 현재 total: 이전 total (3) + mid // time (2) = 5
현재 심사 가능한 최종 인원수(total): 5
<현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 적은 경우
갱신된 left: (mid + 1) = 23
------------------------------
left: 23, right: 29
현재 탐색하는 시간(mid): 26
time: 7, 현재 total: 이전 total (0) + mid // time (3) = 3
time: 10, 현재 total: 이전 total (3) + mid // time (2) = 5
현재 심사 가능한 최종 인원수(total): 5
<현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 적은 경우
갱신된 left: (mid + 1) = 27
------------------------------
left: 27, right: 29
현재 탐색하는 시간(mid): 28
time: 7, 현재 total: 이전 total (0) + mid // time (4) = 4
time: 10, 현재 total: 이전 total (4) + mid // time (2) = 6
현재 심사 가능한 최종 인원수(total): 6
<현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 같거나 많은 경우
갱신된 right: (mid - 1) = 27
------------------------------
left: 27, right: 27
현재 탐색하는 시간(mid): 27
time: 7, 현재 total: 이전 total (0) + mid // time (3) = 3
time: 10, 현재 total: 이전 total (3) + mid // time (2) = 5
현재 심사 가능한 최종 인원수(total): 5
<현재 심사 가능한 인원수(total)>가 [심사해야 하는 인원수(n)]보다 적은 경우
갱신된 left: (mid + 1) = 28
------------------------------
28
"""
