입국심사

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

오늘의 학습 키워드

이진 탐색

• 정렬되어 있는 리스트에서 탐색 범위를 절반씩 좁혀가며 데이터를 탐색한다
• 시작점(left)와 끝점(right)을 기준으로 탐색 범위를 명시한다
• 각 단계마다 탐색 범위가 반으로 감소하므로, 로그(log) 복잡도를 가진다

대표적인 사례

• 매우 넓은(억 단위 이상) 탐색 범위에서 최적의 해를 찾아야 하는 경우
• 데이터를 정렬한 뒤에 다수의 쿼리(query)를 날려야 하는 경우

문제 해결 방법

• 이진탐색을 활용해 모든 심사시간의 최솟값을 구한다
  • r(right)값은 최악의 경우인 n * Math.max(...times)로 설정한다
  • completedCnt는 특정 시간(mid)에 각 심사관이 검사할 수 있는 사람의 수이다
    • 예를 들어, 30분이라는 시간이 주어지고, 각 심사관마다 [7, 10]분이 걸린다고 가정하자
    • 이 경우, completedCnt는 30/7 + 30/10의 결과인 7명이다
  • completedCnt가 구해야하는 값(n)보다 크거나 같다면, r = mid - 1, 작다면 l = mid + 1의 과정을 거쳐 최선의 결과를 찾는다

코드

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

  while (l <= r) {
    const mid = Math.floor((l + r) / 2);
    const completedCnt = times.reduce((acc, cur) => acc + Math.floor(mid / cur), 0);
    completedCnt >= n ? (r = mid - 1) : (l = mid + 1);
  }
  return l;
}