입국심사.md

입국심사

문제 링크

문제 설명

처리시간이 각기 다른 심사대가 있고 n명이 입국심사를 기다리고 있다. 입국심사를 기다리는 사람 수 n 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 주어질 때 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return해라.

주의 사항 : 각 값의 허용값이 굉장히 크다. 시간복잡도를 생각하지 않으면 런타임에러의 위험이 있다.

입출력 예시

Input:
    times: [7, 10]
    n: 6
Output: 28

문제 풀이

각 값의 허용범위가 크기 때문에 브루트 포스로 풀면 안된다. 바이너리 서치를 사용 할 수 있도록 한다 기준을 시간으로 하여 n명을 만족시키는 최소시간을 찾아본다. 시간 범위는 ==1 부터 가장오래걸리는 담당자 처리시간 * n==로 잡는다. 각 시간마다 각 심사위원이 몇명을 처리 할 수 있는지 계산해서 다 더해준다. 그 값이 n이 나올 때까지 검색한다.

풀이 코드 JavaScript

function solution(n, times) {
    let minTime = 1;
    let maxTime = Math.max(...times) * n;
   
    while (minTime  <= maxTime) {
        const midTime = Math.floor((minTime + maxTime) / 2)
        const sum = calculateSum(times , midTime);
        if (sum < n) { 
            minTime = midTime + 1  //위쪽 찾아야 하니까 +1
        } else {
            maxTime = midTime - 1 //아래쪽 찾아야하니까 -1
        }
    }
   
    return minTime;
}

function calculateSum(times , midTime){
    //sum 이렇게 구하는거 대단! 기존 for문 돌림 //시간이라 꼭 Math.floor 써줘야한다
    return times.reduce((acc, time) => acc + Math.floor(midTime / time), 0);
}