[프로그래머스] 입국심사 (Javascript/자바스크립트)

문제

프로그래머스>코딩테스트 연습>입국심사
입국심사

풀이

핵심은 "모든 사람이 심사를 받는데 걸리는 시간을 최소화" 하고 싶다.
제안사항을 보면 사람이나 시간으로 기준을 잡으면 안된다.(범위가 너무 큼)
심사관을 기준으로 삼아야한다.
이 문제를 단순하게 생각해보면 시간을 1분씩 증가시키면서 심사관을 탐색해볼수있다.
O(logN) => 이진탐색
times = > 선형 로그 시간으로도 충분히 가능하다 !

우리는 특정 값을 찾는것이 아니다.
우리가 찾는 것은 "최소 몇 분에 모든 심사가 끝나는가"이다
이런 값을 찾는 것을 결정 문제 라고 한다.
이때 사용하는 알고리즘을 이진탐색이라 부르기도하지만 파라메트릭 서치라고 부른다.

최소 1분에서 10억분 * n 사이에 답이 있다.
면접관들이 몇 명을 처리하는가?
처리 가능한 입국자가 n보다 작다면 분을 올려야되고, 입국자가 n보다 크다면 분을 낮춰야 한다.
면접관이 시간 대비 몇 명을 처리할수있는가?
시간 / 심사시간 = 심사관 당 처리 가능한 입국자 수

function solution(n, times) {
    const sorted = times.sort((a, b) => a - b);
    let start = 1;
    let end = sorted[sorted.length - 1] * n;
    
    
    while (start <= end) {
        const mid = Math.floor((start + end) / 2); 
        //  (시간 / 심사시간 으로 입국자수를 구할수있다.)
        const sum = times.reduce((acc, cur) => acc + Math.floor(mid / cur), 0);

        if (sum < n) {
            start = mid + 1
        } else {
            end = mid - 1;
        }
    }
    
    return start;
}

처음 sum값은 첫번 째 심사위원은 4명처리, 두번 째 심사위원은 3명처리 하기에

1. 중앙값 = (1 + 60) / 2 = 30
   sum = (4 + 3) = 7;
   start = 1; end = 60;
   sum > n이니까 오른쪽 싹다 버리면
   start = 1, end = mid - 1 = 29이다.

2. 중앙값 = (1 + 29) / 2 = 15
   sum = (2 + 1) = 3;
   start = 1; end = 29;
   sum < n이니까 왼쪽 싹다 버리면
   start = 15 + 1 = 16, end = 29이다.

3. 중앙값 = (16 + 29) / 2 = 22
   sum = (3 + 2) = 5;
   start = 16; end = 29;
   sum < n이니까 왼쪽 싹다 버리면
   start = 22 + 1 = 23, end = 29이다.

4. 중앙값 = (23 + 29) / 2 = 26
   sum = (3 + 2) = 5;
   start = 23; end = 29;
   sum < n이니까 왼쪽 싹다 버리면
   start = 26 + 1 = 27, end = 29이다.

5. 중앙값 = (27 + 29) / 2 = 28
   sum = (3 + 2) = 5;
   start = 27; end = 29;
   sum > n 오른쪽 싹다버리면
   start = 27 + 1 = 28; end = 28;
   이므로 start와 end가 같으므로 종료 ! ! !