[알고리즘]입국심사

문제

입국심사

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

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

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

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

제한사항

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

문제풀이

이진 탐색 문제인지 감이 가지 않았던 문제다.
챗지피티와 이 문제에 대한 여러 블로그를 참조한 결과 나온 결론은 심사 시간이 다양하고, 사람의 수가 많을 때 최악의 경우 아주 큰 값이 나올 수 있기 때문이다. 예를들어, 최대 심사 기간이 10분이고 1000명의 사람이 있다면, 최악의 경우 10000분이 나올 수 있다는것.
또한 선형적 데이터 유형에서 최적의 값을 찾는 문제이기 때문에 이진 탐색이 알맞은 것이다.

코드_내가 푼 코드

function solution(n, times) {
    let left = 1;
    let right = Math.max(...times) * n;

    while(left <= right) {
        let mid = Math.floor((left + right) / 2);
        let totalPeople = 0;
        
        times.forEach(time => totalPeople += Math.floor(mid / time));

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

1. 이진 탐색을 사용할 것이므로 기준이 되는 left(min)값과 right(max) 변수를 선언. 1분 이상이기 때문에 left값은 1이 되고, 해당 문제에서 최악의 경우 가장 크게 나올 수 있는 경우 주어진 times 배열 내 최대 수 * n 이기 때문에 이 값을 right값으로 설정한다.
2. 최대 경우의 수까지 while문에서 루프를 돌린다.
3. 중간값과 해당 경우에서 나올 수 있는 입국 심사를 받을 수 있는 사람의 수를 변수로 정의한 후 입국 심사를 받을 수 있는 사람의 수를 구한다.
4. forEach문이 끝난 후 입국 심사를 받을 수 있는 사람의 수(totalPeople)가 입국 심사를 기다리는 사람 수(n) 보다 작을 경우 left 값을 우측으로 옮기고, 같거나 작을 경우 right 값을 왼쪽으로 옮긴다.
5. 모든 과정이 마무리된 후 left값을 반환한다.

노트

어떻게 보면 그렇게 어려운 개념은 아니지만 문제의 포인트를 짚고 기준이 되는 숫자들을 설정하는게 어렵다고 느꼈다. 알고리즘 공부하며 중간중간 돌아봐야할 문제🥹