문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
풀이
문제의 목적은 "모든 사람이 심사를 받는데 걸리는 시간의 최솟값" 을 구하는 것이다.
먼저 임의의 시간을 설정해 몇 명이 심사를 받을 수 있는지 확인하고 그 시간을 최소화해야 한다.
이진 탐색을 활용해 최소 시간과 최대 시간을 설정해 중간값을 찾는다. n명 이상 심사 가능하면 중간값 기준 왼쪽 범위를 탐색하고 n명 미만 심사 가능하면 중간값 기준 오른쪽 범위를 탐색하면 된다.
먼저 시간 리스트를 정렬했다. 여기서 sorted() 가 아닌 sort() 함수를 사용한 이유는 times의 원본 리스트가 중요한 값이 아니기 때문이다.
times.sort() left 에 최소 시간을 넣고 right 에 최대로 걸리는 시간을 넣는다.
left = min(times) # 최소값
right = max(times) * n # 최대값이제 아래와 같이 right 의 시간이 left 의 시간보다 커질 때까지 루프를 실행한다.
while left <= right:
mid = (left + right) // 2 # 중간값
passed = 0 # 통과 인원수
for time in times:
passed += mid // time # 시간별 통과 인원수 합계
if passed >= n: # 모두 심사에 통과되면 break
break
if passed < n: # 모든 사람이 심사를 통과하지 못한 경우
left = mid + 1
continue
right = mid - 1
answer = mid