프로그래머스[Level 3] 입국심사 (이진탐색, 결정알고리즘)

문제

제한 사항

입출력 예

풀이

function count(times, mid) {
  const cnt = times.reduce((a, c) => a + Math.floor(mid / c), 0);
  // 60분이라 치면 60/7 + 60/10 = 14, 총 14명이 심사를 받게된다.
  return cnt;
}
function solution(n, times) {
  let answer = 0;
  times.sort((a, b) => a - b);
  let lt = 0; // 최소값은 0
  let rt = times[times.length - 1] * n; // 전부다 긴 시간쪽에서 입국심사를 받을 경우

  while (lt <= rt) {
    let mid = Math.floor((lt + rt) / 2);
    let cnt = count(times, mid);
    if (cnt >= n) {
      answer = mid;
      rt = mid - 1;
    } else {
      lt = mid + 1;
    }
  }
  return answer;
}

이진탐색을 이용한 결정 알고리즘이다.

답이 될 수 있는 조건과 mid값과 count 함수의 관계를 먼저 파악하기

답이 될 수 있는 조건은 사람 수가 6명 이상이여야한다.
이 문제의 경우 mid값이 증가하면 count도 증가한다. 그럼 count 값을 줄일려면 mid값도 줄어들어야하니 rt가 작아져야한다.