[이분탐색] 프로그래머스 '입국심사' - js

1. 문제

https://school.programmers.co.kr/learn/courses/30/lessons/43238?language=javascript 

프로그래머스

2. 코드

수가 크고, 정해진 정답이 있을 때에는 이분탐색을 사용해야 한다고 한다.

1분부터 10^18분까지 중에서 이분탐색을 통해 n명의 입국심사 대기자를 심사할 수 있는 최적의 시간을 찾아야 한다. 최소 시간은 1분, 최대 시간은 가장 오래걸리는 심사시간 * 입국심사를 기다리는 사람이다. 

" 이 사이의 숫자 중 어떤 게 모든 사람을 심사하되 최소한의 시간이 걸리도록 하는 답이 될까? " 이분탐색이 이 질문에서부터 시작된다. 최소값과 최대값의 중간에서부터 탐색해 나가는 것.

예를 들어, times가 [7, 10]일 때 30분(최소값 : 1, 최대값 : 60, mid : 30) 동안 심사관이 쉬지 않고 심사를 계속 했다고 가정하면 7분이 걸리는 심사관은 4명을 심사하고 10분이 걸리는 심사관은 3명을 심사할 수 있다. 30분 동안에 최대 7명을 심사할 수 있는 것이다.

심사 받아야할 사람은 6명이니 답은 mid보다 작은 값이 될 것이다 => high = mid -1
만약 심사 가능한 사람이 n보다 작다면 답이 mid보다 큰 값이 될 것이다 => low = mid + 1

이런 방식으로 쭉 검사하다가 people < n이 되어 low를 mid+1로 증가시킨 후, low가 high보다 크다면 더 이상 탐색할 이유가 없으므로 while문을 종료한다.

function solution(n, times) {
    let low = 1;
    let high = Math.max(...times) * n;
    while (low <= high) {
        const mid = Math.floor((low + high) / 2);
        // 각 심사관 별로 심사에 걸리는 시간으로 경과 시간을 나눠서 그 몫을 구하여 전부 더한 수 = X분일 때 심사 가능한 최대 인원의 수
        const people = times.reduce((acc, time) => acc + Math.floor(mid / time), 0);
        if (people < n) {
            low = mid + 1;
        } else {
            high = mid - 1;
        }
    }
    return low;
}

 

이해에 도움이 됐던 블로그)

https://tesseractjh.tistory.com/298

[프로그래머스 Level 3] 입국심사 - JavaScript

 

내 첫 이분탐색 문제.. 처음에는 왜 이분탐색으로 풀어야하는지도 이해가 안됐다. 차분히 몇 개의 풀이 글을 읽어보니 이제 왜 이분탐색으로 풀어야하는지까지는 이해됐다. 막상 문제 던져주면 못 풀듯 ㅠㅠ 어렵다 이분탐색