프로그래머스 👉🏻 입국심사


문제 설명

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

  • 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있다.
  • 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있다.

제한사항

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

입출력 예시

n times return
6 [7, 10] 28
  • times 배열의 길이는 입국 심사대의 개수
  • times의 각 요소는 심사관의 소요시간 (1번 심사관은 7분이 걸리고, 2번 심사관은 10분이 소요된다.)
  • 가장 첫 두 사람은 바로 심사를 받으러 갑니다.
  • 7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
  • 10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
  • 14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
  • 20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

문제 이해하기

문제를 봤을 때 이진 탐색으로 풀어야겠다라는 생각조차 들지 못한 문제였습니다…ʕ ´•̥̥̥ ᴥ•̥̥̥`ʔ
왜 이진 탐색으로 풀어야하는지에 대한 추론부터 해보자구요!

우리는 특정 값을 찾는 것이 아니라 최소 몇 분에 모든 심사가 끝나는지 최소값을 찾으려고 합니다. 즉, 우리가 원하는 조건에 가장 일치하는 값을 찾아내는 결정문제입니다. 이 문제는 파라메트릭 서치(Parametric Search)를 이용해서 풀어야하죠. 파라매트릭 서치는 이분탐색과 매우 유사합니다. 차이점이라면 결정 문제인지 아닌지의 차이에 있습니다.

제한 사항을 보면 최대 인원 수와 최대 소요 시간이 10억인 것을 볼 수 있습니다. 이렇게 큰 숫자가 나온다면 해결 방법은 한 가지밖에 없다는 것을 알아둬야합니다. 선형 시간은 불가능하고 log 시간이 걸리는 알고리즘 을 사용해야합니다.

log 시간이 걸리는 알고리즘엔 무엇이 있을까요?
바로 이진 탐색입니다. 이진탐색트리의 조건은 배열이 정렬되어있어야 한다인데요, times의 최대 길이는 10만이기 때문에 선형시간으로 정렬해도 문제가 없습니다.


그럼 이제 어떻게 풀어야할지 고민해봅시다.

총 걸리는 시간의 최소 시간은 1분이고 최대 시간은 가장 오래걸리는 사람이 n명을 검사했을 때의 값이 됩니다. 이 사이에 답이 있다는 건 확실한데… 또 무엇을 고려해야할까요?

또 알아야 할 것은 면접관들이 몇 명의 입국자를 처리할 수 있는가?입니다. 만약 처리 가능한 입국자 수가 n보다 작다면, 분(걸리는 시간)을 올려야하고 n보다 크다면 분을 줄이면 될 것 같습니다.

면접관이 시간 대비 몇 명을 처리할 수 있는가는 어떻게 알 수 있을까요? 시간 / 심사시간을 하게되면 심사관 당 처리할 수 있는 입국자 수가 나옵니다. 이것들을 이용해서 이분법으로 좁혀나가면 최소 시간을 구할 수 있습니다.

코드로 구현해봅시다 🐥

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
function solution(n, times) {
  const sortedTimes = times.sort((a, b) => a - b);
  let left = 1; // 최소 시간
  let right = sortedTimes[sortedTimes.length - 1] * n; // 최대 시간

  // 이진탐색 loop
  while (left <= right) {
    // 중간 값 구하기
    const mid = Math.floor((left + right) / 2);
    // 시간 / 심사시간으로 입국자 수 구한 후 모두 더하기
    const sum = times.reduce((acc, time) => acc + Math.floor(mid / time), 0);

    if (sum < n) {
      left = mid + 1;
    } else {
      right = mid - 1;
    }
  }

  // return값은 역전되기 직전에 더해진 값을 반환하면 된다.
  return left;
}

Review

이진탐색트리의 개념은 그렇게 어렵지 않다고 생각했는데 막상 문제를 풀어보니 어떤 문제에 이진 탐색을 써야하는지를 모르겠어서 더 어려웠던 것 같습니다. 여러 유형의 이진 탐색 문제를 풀어보면서 익숙해져야 할 것 같습니다.