서문

이번 문제는 이진탐색 알고리즘을 사용해야 하는 것을 알았음에도 불구하고 애를 먹은 문제다. 이진탐색 알고리즘 자체는 간단해서 어렵지 않았지만, 문제는 어떻게 어떤 방식으로 적용시켜야 하는지 감이 잡히질 않았다.

데이터들의 크기가 커서 일반적인 방식으로 접근하면 시간초과가 난다는 것을 쉽게 알수 있기에 더욱 고민을 많이 했다. 하지만 고민을 아무리해도 감이 안잡혀서 이대로 시간을 보내기보다는 한 번 다른 사람의 풀이를 보고 이해한 후 푸는 것도 좋은 방법이라 생각해 다른 분들의 코드를 살펴보았다.

소스 코드

먼저 소스 코드를 첨부하겠다.

function solution(n, times) {
  let answer = Number.MAX_SAFE_INTEGER; // 모든 사람이 입국심사를 마치기까지 걸린 시간

  times.sort((a, b) => a - b); // 이진탐색을 하기 위해 오름차순 정렬을 해준다
  let left = times[0]; // 최소로 걸리는 시간
  let right = times[times.length - 1] * n; // 최대로 걸리는 시간

  // left가 right를 넘어가면 종료
  while (left <= right) {
    const mid = parseInt((left + right) / 2); // 중간 값
    let count = 0;

    // 각 입국심사관마다 제한시간동안 몇 명 처리 가능한지 세어주고 count에 더해준다
    times.forEach(time => {
      count += parseInt(mid / time);
    });

    // count가 입국심사 대기자들보다 많거나 같으면 차고 넘침이 있는 것이므로 최대 값을 줄여서 다시 테스트한다.
    // 같을 때도 하는 것은 정확한 하나의 값을 찾기 위해 줄이는 것이다.
    // 각각 -1과 +1을 해주는 것은 해당 mid값은 이미 검사했기 때문이다.
    if (count >= n) right = mid - 1;
    else if (count < n) left = mid + 1; // 작을 때는 최소 값을 늘려서 테스트한다.

    // 설정된 mid값으로 모든 인원이 검사가 가능하면 기존 값과 비교해 작은 값으로 대체한다.
    if (count >= n) {
      answer = Math.min(answer, mid);
    }
  }

  return answer;
}

코드 설명

이진탐색 알고리즘을 사용하기 때문에 먼저 오름차순으로 정렬을 해주었다. 그 후, 최솟값과 최댓값을 설정해주었는데, 이 때 최댓값은 가장 오래걸리는 입국심사원이 모든 인원을 검사할 때 걸리는 시간이므로 이 값으로 설정해주었다. 최솟값은 입국심사 대기자가 1명일 때, 가장 빠른 입국심사원이 검사한다는 가정으로 생각하고 설정해주었다. 참고로 최솟값은 left, 최댓값은 right이다.

그 후, 두 값의 가운데 값을 계산한다. 이 값은 최소로 걸리는 시간과 최대로 걸리는 시간의 중간값이다. 이 정도의 시간이 주어진다고 가정했을 때, 각각의 입국심사원들은 몇 명의 입국심사 대기자를 심사할 수 있는지 계산해 count 변수에 더해주었다.

그 다음 count(mid라는 시간이 주어졌을 때, 최대로 심사가능한 수)를 매개변수로 주어지는 n값과 비교해준다. count가 n보다 크거나 같으면 mid라는 시간동안 모든 인원이 심사를 받을 수 있다는 것이다. 반대로 count가 n보다 작으면 mid라는 시간동안 전부 검사를 하지 못한다는 상황이다.

그래서 count가 n보다 크거나 같으면 right = mid - 1을 해주고, count가 n보다 작으면 left = mid + 1을 해주게 된다. 이 때, 1을 빼고 더하는 것은 mid 값 자체는 이미 검사를 했기 때문에 범위에서 제외하는 것이다.

위의 순서를 left <= right라는 조건이 만족할 때 까지 반복하면서, 제일 작은 mid 값을 찾아주면 그게 바로 정답이 된다.

후기

이 문제는 내 사고가 얼마나 좁은지 알 수 있게 해주는 문제였다. 이진탐색이라는 알고리즘 자체는 이해하고 있었으나, 이를 적절히 활용할 수는 없었던 나의 두뇌에 대해 반성해야겠다. 앞으로 문제를 다각적으로 바라보는 연습도 많이 필요할 것 같다.