[이진 탐색] 입국심사

지은·2023년 4월 7일

Algorithm

목록 보기

19/33

문제

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

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

문제 해석

입국심사를 해야하는 사람의 수(n)가 최대 10억 명까지이므로, n을 이용해서 풀면 시간이 너무 오래걸릴 것이므로 times를 이용해서 풀어야 한다.

이때 이진 탐색을 이용해서 임의의 시간(중간값)을 정한 뒤, 이 임의의 시간이 부족하면 시간을 늘리고, 시간이 남으면 시간을 줄이는 방법으로 범위를 점점 반으로 좁혀나가 최소한의 시간이 걸리는..! 최적의 시간을 찾아야 한다.

left : 입국 심사 처리에 가장 짧게 걸리는 시간 (1분)
right : 입국 심사 처리에 가장 오래 걸리는 시간
➡️ times 배열에서 가장 오래 걸리는 입국심사원이 모든 인원(n)을 처리하는 경우
mid : 반복문을 돌면서 때려맞춰볼 임의의 시간..

입출력 예를 예시로 풀어보면,

left : 1분 (입국 심사 걸리는 시간의 최솟값)
right : 10 * 6 = 60분 (입국 심사에 걸리는 시간 최댓값)
mid : Math.floor(61 / 2) = 30분

그러면 이제 30분 동안 입국 심사관들이 처리할 수 있는 인원의 수가 6명과 맞아떨어지는지 확인하면 된다.

입국 심사관들이 30분동안 처리할 수 있는 인원의 수
7분 걸리는 심사관 : 30 / 7 = 4명
10분 걸리는 심사관 : 30 / 10 = 3명
➡️ 총 7명

시간이 남는다!
이 뜻은 30분이 최소 시간이 아니라는 뜻이므로 30분보다 시간을 더 줄여서 다시 계산해봐야 한다.

left : 1분
right : 29분 (mid - 1로 right를 다시 할당한다.)
mid : Math.floor(30 / 2) = 15분

그러면 이제 다시 15분 동안 입국 심사관들이 처리할 수 있는 인원의 수가 6명과 맞아떨어지는지 확인해보자.

입국 심사관들이 15분동안 처리할 수 있는 인원의 수
7분 걸리는 심사관 : 15 / 7 = 2명
10분 걸리는 심사관 : 15 / 10 = 1명
➡️ 총 3명

시간이 부족하다...
그러면 15분보다는 더 시간이 필요하다는 뜻이다. left를 mid + 1로 다시 할당해서 다시 계산해보자.

left : 16분
right : 29분
mid : Math.floor(45 / 2) = 22분

22분 동안 입국 심사관들이 처리할 수 있는 인원의 수가 6명과 맞아떨어지는지 확인해보자.

입국 심사관들이 22분동안 처리할 수 있는 인원의 수
7분 걸리는 심사관 : 22 / 7 = 3명
10분 걸리는 심사관 : 22 / 10 = 2명
➡️ 총 5명

부족하다. 다시 left를 mid + 1로 옮겨서 다시 계산해보자.

left : 23분
right : 29분
mid : Math.floor(52 / 2) = 26분

입국 심사관들이 26분동안 처리할 수 있는 인원의 수
7분 걸리는 심사관 : 26 / 7 = 3명
10분 걸리는 심사관 : 26 / 10 = 2명
➡️ 총 5명

부족하다. left를 mid + 1로 옮긴다.

left : 27분
right : 29분
mid : Math.floor(56 / 2) = 28분

입국 심사관들이 28분동안 처리할 수 있는 인원의 수
7분 걸리는 심사관 : 28 / 7 = 4명
10분 걸리는 심사관 : 28 / 10 = 2명
➡️ 총 6명

6명이다! 하지만 아직 left와 right가 같아지지 않았으므로 반복문은 다시 돌아가야 한다. 이 경우에는 right를 mid - 1로 옮겨준다.

left : 27분
right : 27분
mid : Math.floor(56 / 2) = 28분

입국 심사관들이 27분동안 처리할 수 있는 인원의 수
7분 걸리는 심사관 : 27 / 7 = 3명
10분 걸리는 심사관 : 27 / 10 = 2명
➡️ 총 5명

부족하다. left를 mid + 1로 옮긴다.
하지만 이렇게 되면 left = 28가 right = 27보다 커지게 되므로 더 이상 반복문에 들어가지 않고, 결과값인 28을 리턴하게 된다.

풀이

function solution(n, times) {
  const sortedTimes = times.sort((a, b) => a - b);     // 이진 탐색을 사용하기 위해서 정렬해준다.
  let left = 1;                                        // 1명을 심사하는데 걸리는 최소 시간은 1분
  let right = sortedTimes[sortedTimes.length - 1] * n; // 가장 느린 심사관이 모든 사람을 처리할 때 걸리는 시간
  
  while (left <= right) { // left와 right가 같아질 때까지 반복한다.
    const mid = Math.floor((left + right) / 2); // 중간값
    const sum = times.reduce((acc, time) => acc + Math.floor(mid / time), 0); // 심사들의 심사시간의 총합을 구한다.
    
    if (sum < n) {     // 이 총합이 n보다 작다면
      left = mid + 1;  // 시간을 늘려준다.
    } else {           // 시간이 더 길다면
      right = mid - 1; // 시간을 줄인다.
    }
  }
  
  return left;
}