[Programmers / JS] Lv. 3 입국심사

https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는 데 걸리는 시간은 다릅니다.

처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는 데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는 데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해 주세요.

제한사항

• 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
• 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
• 심사관은 1명 이상 100,000명 이하입니다.

 

입출력 예

n                                         times                                                                                       return

6

[7, 10]

28

 

 

Solve

• times를 활용하기 위해 오름차순으로 먼저 정렬을 해줬습니다. 최소 시간을 1, 최대 시간을 times의 마지막 원소에 사람 수(n)를 설정하였습니다. (입국심사 시간이 최대인 사람에게 모두 입국 심사를 받는 것이 최대)
• 현재 설정된 시간(mid) 내에 심사를 받을 수 있는 최대 사람의 수를 구하기 위하여, 가장 짧은 시간부터 설정된 시간 내에 몇 명까지 가능한지 구해줍니다. (mid / times[i]를 해주는 이유)
• 주어진 n보다 더 많은 사람을 심사할 수 있다면 범위를 줄여주고, 더 적거나 같다면 범위를 넓혀줌으로써 최적화된 값을 찾아갔습니다.

Code

function solution(n, times) {
    times.sort((a,b)=>a-b);

    let left = 1;
    let right = times[times.length-1] * n;
    let mid = Math.floor((left + right)/2);

    while(left < right) {
        let count = 0;
        for(let i = 0; i < times.length; i++) {
            const value = Math.floor(mid / times[i]);
            if(value === 0) break;
            count += value;
            if(count > n) break;
        }

        if(count < n) {
            left = mid + 1;
        } else {
            right = mid;
        }
        mid = Math.floor((left + right)/2);
    }
    return mid
}