프로그래머스 - Lv.3 입국심사 (이분탐색) node.js

https://school.programmers.co.kr/learn/courses/30/lessons/43238

해당 문제는 입국하고자 하는 사람의 수 n, 각각의 심사관이 처리할 수 있는 시간을 담은 배열 times가 주어질 때, 걸리는 시간을 가장 최소화한 값을 구하는 문제다. 심사를 원하는 인물이 최대 10억 명, 걸리는 시간이 최대 10억 분이므로, 자연스레 이분탐색으로 풀이를 해야 한다.

추가적으로 아래는 위와 비슷한 문제지만, 백준에서 출제한 이분탐색으로 최댓값 구하는 문제니 필요하다면 참고하길 바란다.

2023.12.08 - [개발/algorithm] - 백준2805 - 나무 자르기 (이분탐색) node.js

 

문제 풀이 방식

이분탐색에서 활용하기 위한 최소 범위와 최대 범위를 설정한다. 이때, 최소한으로 걸리는 시간은 문제에서 제시된 것처럼 1분, 최대한으로 걸리는 시간은 심사관 중 가장 오래걸리는 사람이 n명의 인원을 모두 심사하여 처리할 때가 최대범위가 된다. (즉 해당 이분탐색은 시간을 중심으로 탐색을 진행하는 것이라 보면 된다.)

이후, while 문에서는 중간값(시간)을 구한 뒤, 해당 중간값으로 심사관이 총 몇 명을 처리할 수 있는지를 구한다. 

그리고 이 처리할 수 있는 인원을 persons 이라고 할 때, 해당 값이 문제에서 입국심사를 처리하고자 하는 인원인 n보다 크거나 같다면 최대 범위를 수정, 작다면 최소 범위를 수정하여 범위를 줄여나가는 방식으로 탐색을 진행한다.

이전에서 포스팅 한 적 있지만, 같을 경우 리턴하는 방식이 아니라, 같거나 다를 경우를 조건으로 하여 끝까지 탐색을 진행하는 이유는 최적의 값이 아닌 최소의 값을 찾고자 함으로, 값을 최대한 낮출 수 있도록 최대 범위 end를 우선적으로 수정해나가는 것이라 보면 된다.

이때 리턴되는 값인 start 는 모든 탐색이 완료되었을 때 조건을 만족하는 최솟값이 담겨있는 변수가 된다.

 

전체 소스 코드

function solution(n, times) {
  let start = 1;
  let end = Math.max(...times) * n;

  while (start <= end) {
    const mid = Math.floor((start + end) / 2);
    const persons = times.reduce((ac, cur) => ac + Math.floor(mid / cur), 0);
    persons >= n ? (end = mid - 1) : (start = mid + 1);
  }

  return start;
}

console.log(solution(6, [7, 10]));