[알고리즘] 이진탐색과 파라메트릭 서치 (입국 심사 문제)

문제

기록 및 풀이

1. 해당문제가 이진탐색문제로 접근해야 하는 문제인지 처음에 오래걸렸다. 구하려고 하는 최소시간이 어떻게 산출되는지 이해가 늦어졌기 때문이었고, 특정값을 구하는 이진탐색과는 다르게 해당 문제는 어떤 조건을 만족하는 최소값을 구하는 문제이기 때문이다. 그러나 이진탐색은 (값이 정렬되어있을 때) 특정 값을 구하는 데에 최적화 되어 있지만 , 탐색의 대상이 되는 대상의 범위를 좁히는 데에도 유용하다. 이러한 로직으로 범위를 줄여나가 원하는 조건을 답을 찾을 수도 있는데, 이러한 방식을 파라메트릭 서치(Parametric Search) 라고 한다. 자세한 내용은 이 분의 블로그에 정리되어있다.

2. 중요한건 최대 10만명의 심사관 중에서, 최대 10억분이 소요되는 심사관까지 있다는 것이다. 조건에 모든 심사관이 반드시 한명이상 심사를 해야한다는 조건이 없기 때문에, 이는 가장 적은 시간이 걸리는 심사관이 심사를 최대한 많이 하고, 그 소요시간 안에 다른 심사관들이 몇 개의 심사를 할 수 있느냐의 문제이다.

3. 말그대로 모든 심사관이 한명 이상 심사를 해야한다는 조건이 없기 때문에, 어떤 심사관이 심사를 할 수 있던 말던 상관이 없다. 고로 시간을 기준으로 탐색해 나가면 된다.

4. 1분씩 10억분까지 선형탐색해나간다면 절대 답을 찾을 수 없을 것이다. 그래서 이진탐색을 활용했다. O(logN)의 시간복잡도는 여전히 선형적인 시간보다 훨씬 효율적이다.

5. 가장 헷갈렸던 점은, 시간이 기준이라면 루프탈출조건을 만드는 것인데 n명이 통과되는 시점엔 그 시간이 최대값이 아닐 수 있기 때문이다.
   ex) 입출력 예를 보면 29분에도 6명이 탈출한다.

6. left, right, mid는 전부 시간이며, 이를 기준으로 심사를 통과된 사람이 같을때 루프를 나오게 하는 것이 아니라, 같을때 또한 right를 mid-1를 해준다면 결국 right는 정답의 직전값에서 최대값을 형성할것이고, left = right 가 될때까지 left는 같아지게 된다. left = right = mid가 같을 때또한 심사를 통과하는 인원은 결국 n 보다 작을 것이기 때문에 left = mid + 1 이되며 탈출 조건에 의해 루프를 탈출한다.
   결국 정답은 left를 return 해주면 된다

내 정답

function solution(n, times) {    
    times.sort((a,b)=>a-b);
    
    let left = 1;
    let right = times[times.length-1] * n;
    
    while(left<=right){
        let mid = Math.floor((left + right)/2);
        let acc = 0;
        for(let i = 0; i<times.length; i++){
            acc += Math.floor(mid / times[i]);
        }        

        if(acc < n) {
            left = mid + 1 ;
        }
        
        if(acc >= n) {
            right = mid - 1;
        } 
    }
    return left;
}