프로그래머스 데브코스 - [3단계] 입국심사

 

문제 설명

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

 

입출력 예 설명

가장 첫 두 사람은 바로 심사를 받으러 갑니다.

7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.

10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.

14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.

20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.

 

풀이

문제의 읽기 전, 제한사항을 먼저 읽어볼 필요가 있다. 입국심사를 기다리는 사람은 최대 10억명으로 보편적인 입력값이 아님을 알 수 있다 보통 1억개 이상의 입력값이 주어지면 O(logn)시간에 처리하기 위해 이진 탐색을 사용하는 경우일 확률이 높다.

또한 문제를 읽어보면 요구하는 리턴 값은 '모든 사람이 심사를 받는데 걸리는 시간의 최솟값'이다. 이는 전형적인 'X의 조건을 만족하는 최솟/최댓값'의 유형인 결정문제이다. 결정문제는 이진탐색으로 풀어낼 수 있다. 이러한 문제는 파라메트릭 서치(Parametric Search)라고 불린다.

나올 수 있는 모든 사람이 심사를 받는데 심사를 받는데 걸리는 시간은 최소 1분에서 최대 (10억 * n)분 사이이다.

시간을 1분과 10억*n 분의 평균 값으로 지정해 두고 이진 탐색을 시작해 나간다.

(시간 / 심사시간)은 심사관 당 처리 가능한 입국자 수이므로 처리 가능한 입국자 n보다 적다면, 시간을 올려야되고, 입국자가 n보다 크다면 시간을 낮춘다.

function solution(n, times) {
    // 심사관당 걸리는 시간을 오름차순 정렬
    const sortedTimes = times.sort((a, b) => a - b);
    // 최소 1분
    let left = 1;
    // 최대 가장 오래 심사하는 심사관의 시간 * n
    let right = sortedTimes.at(-1) * n;
    
    // 이진 탐색 시작
    while (left <= right) {
        // left와 right 중간 값
        const mid = Math.floor((left + right) / 2);
        // 각 심사관당 처리 가능한 입국자 수를 모두 더함
        const sum = sortedTimes.reduce((acc, time) => acc + Math.floor(mid / time), 0);
        
        // 심사관당 처리 가능한 입국자 수를 모두 더한 값과 n 비교
        if(sum < n) {
            left = mid + 1;
        } else {
            right = mid - 1;
        }
    }
    
    return left;
}

 

후기

상당히 난이도가 있었던 문제여서 풀지 못하고 풀이법을 보고 찬찬히 이해를 했다. 처음 이 문제를 접했을 때 분야가 이진 탐색이었기 때문에 이진 탐색을 사용해서 풀어야 한다는건 알고 있었지만 왜 그래야 하는지 이해를 하지 못했다. 10억개의 터무니없는 입력값이며 X의 조건을 만족하는 최솟/최댓값의 유형의 문제는 파라메트릭 서치를 해야한다 라는걸 이해하지못하고 외우려고 했던 탓인 것 같다.

그러던 차에 다른 포스트에서 결정문제, 파라메트릭 서치의 접근방식을 이해할 수 있는 예시가 있었는데 입력값이 너무 많다보니 대충대충 보자는 말이었다. 대충 중간값을 만들어놓고 중간값이 원하는 값보다 크면 중간값보다 작은 무리에서 다시 중간값을 대충 정해서 구하고 중간값이 원하는 값보다 작으면 중간값보다 큰 무리에서 다시 중간값을 대충 정해서 구하자는 말이었다. 그제서야 입력값이 1억 이상으로 너무 클 때 이진 탐색을 써서 문제를 풀 확율이 높다는 강사님의 말씀을 이해할 수 있었다.