이분탐색_Lv3_입국심사

문제

풀이

• 정답의 범위가 정해져있고 특별한 규칙이 없이 탐색을 통해 결과를 도출해야하는 경우 이분 탐색을 사용한다.

• 해당 문제에서는 정답의 범위의 최대 값이 '가장 오래 걸리는 심사관 * 승객 수'이다.

• 이분탐색을 진행하며 해당 시간에 모든 심사 관들이 최대로 할 수 있는 심사 횟수를 계산하고

• 심사 횟수가 승객 수에 근접하고 가장 시간이 적게 걸리는 경우를 return 한다

코드

function solution(n, times) {
    times.sort((a,b) => a-b);
    let res = -1;
    let rt = times[times.length-1] * n;
    let lt = 0;
    
    while (lt<=rt){
        let mid = Math.floor((rt+lt) / 2);
        let max = 0;
        
        for (let e of times){
            //모든 심사관의 최대 심사 횟수를 계산
            max += Math.floor(mid / e);
        }
        
        if(max >= n){
            //초과해서 가능할 경우
            res = mid;
            rt = mid - 1;
        }else{
            //심사가 완료가 불가능한 경우
            lt = mid + 1;
        }
    }
    return res;
}