입국심사 (level 3)

링크

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

문제

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

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

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

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

문제 이해

이 문제는 이분탐색 알고리즘을 구현하여 특정 시간동안 각각의 심사관들이 심사할 수 있는 사람의 수를 계산하여 모두 더하는 것으로 해결이 가능하다.

문제 해결에 최소로 걸리는 시간을 left, 최대로 걸리는 시간을 right로 하여 mid 값을 정하고, 해당 mid 시간동안에 각각의 심사관들이 심사하는 사람의 수를 구한다.

계산 결과, 모두 더한 값이 n보다 작으면 주어진 시간 mid 동안에 n 만큼의 사람을 모두 처리하지 못했음을 의미하고, 모두 더한 값이 n보다 크면 주어진 시간 mid 동안에 n 만큼의 사람을 모두 처리하고도 시간이 남았음을 의미한다. 이렇게 해서 각각의 결과에 대해서 left와 right 값을 변경해 나가며 시간을 계산한다.

코드

// n => 입국심사 대기 사람 수
// times => 심사관이 심사하는데 걸리는 시간 집합

function solution(n, times) {
    // 최소로 걸릴 수 있는 시간 left, 최대로 걸릴 수 있는 시간 right
    let left = 1
    let right = Math.min(...times) * n
    
    while (left <= right) {
        let mid = Math.floor((left + right) / 2)
        let people = times.reduce((acc, cur) => acc + Math.floor(mid / cur), 0)
        // people은 mid 시간 동안 처리 할 수 있는 사람의 수
    
        // people이 n보다 작다는 것은 아직 처리해야할 사람이 남았다.
        // people이 n보다 크거나 같다는 것은 처리해야 할 것이 끝났다.
        // 이 간격을 최소로 좁히는 것이 목표.
        if (people < n) {
            left = mid + 1
        } else {
            right = mid - 1
        }
    }
    // left 가 right를 넘어갔다는 것은 left가 n보다 크거나 같아져서 n명을 수용할 최소값이 되있다는 것이다.
    return left;
}