[JS] 입국심사 - 왜 이게 이진 탐색인지 알려드림

파라메트릭 서치에 관한 문제입니다.

이런 문제 유형을 접하는게 쉽지 않아서 어떤 점에서 힌트를 얻을 수 있고,

또 이진 탐색을 적용하는 방법론적인 이야기를 해볼까합니다.

 

그러면 같이 한번 보죠!

---

문제 요약

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

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

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

 

제한사항

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

 

테스트케이스

n	times	return
6	[7, 10]	28

 

접근 방법

혹시 n을 1씩 빼가면서 times에 넣고 타이머를 동시에 돌리면서 scheduler를 돌리려했나요?

그건 일단 시간 초과가 날껍니다.

 

제한사항에서 기다리는 사람은 최대 1억 명, 그리고 한 사람을 심사하는데 걸리는 시간은 최대 1억 분입니다.

기다리는 사람이나 심사시간 기준으로는 loop를 돌리지 말라는 제한사항입니다.

그나마 심사관의 수(times 배열의 갯수)가 최대 100,000 명이네요. 루프를 돌린다면 이쪽이 그나마 현실성 있어보입니다.

 

파라메트릭 서치에 대해서 먼저 말씀드리려고 합니다.

 

파라메트릭 서치

1. 원하는 답이 속한 범위를 정한다.
2. 범위를 줄여가면서 원하는 답이 나올때 까지 조절한다.

이런 방법을 최적화 문제를 결정 문제로 바꾸어서 푼다고 한다.

 

우리가 return해야하는 모든 사람이 심사를 받는데 걸리는 시간의 최솟값이 속하는 배열의 최솟값은 어떤 값일까요?

1이 될수도 있겠고, times 배열의 최솟값이 될 수 도 있겠네요.

그렇다면 최댓값은 어떨까요? 이건 좀 명확하네요. times 배열의 최댓값에 n을 곱한 값입니다.

 

이 배열의 모든 값들은 심사를 받는데 걸리는 시간을 의미합니다.

이진 탐색을 통해 mid 값을 구해주고 그 시간동안 심사가능한 사람의 수를 구해준다면?
(mid = 30일때, 7분이 걸리는 심사관은 약 4.3명, 10분이 걸리는 심사관은 3명을 검사할 수 있겠네요. 사람이 소숫점일리는 없으니 7명을 검사한다고 말할 수 있겠습니다.)

 

이 배열의 각 끝값이 같아질 때까지 루프를 돌려볼겁니다. 그렇다면 원하는 답을 얻어낼 수 있겠군요.

정답 코드

function solution(n, times) {
    const sorted = times.sort((a, b) => a - b);
    let [lp, rp] = [sorted[0], sorted[sorted.length - 1] * n];
    
    while (lp <= rp) {
        let mid = Math.floor((lp + rp) / 2);
        const sum = sorted.reduce((acc, val) => acc + Math.floor(mid / val), 0);
        
        if (sum >= n) rp = mid - 1;
        else lp = mid + 1;
    }
    
    return lp;
}

 

팁 1. sum과 n의 관계성에 대해서

let mid = Math.floor((lp + rp) / 2);
const sum = sorted.reduce((acc, val) => acc + Math.floor(mid / val), 0);

if (sum >= n) rp = mid - 1;
else lp = mid + 1;

 

전 이 문제를 처음 접했을 때 이 sum과 n의 관계성을 생각해내는게 어려웠었는데요.

천천히 접근해보면 그나마 이해가 됩니다. 아까 말씀드린 대로 mid는 모든 심사를 완료하기 까지 걸리는 어떤 임의의 시간입니다.

우리가 비교할 수 있는 n은 총 심사해야하는 사람입니다.

이 시간을 어떻게 사람으로 바꿀 수 있을까요?

총 걸리는 시간에서 각 심사관이 한 사람을 심사할 때 걸리는 시간, 즉 times의 각 요소를 나눠주면 그 시간안에 검사할 수 있는 사람의 수를 구할 수 있습니다.

 

 

파라메트릭 서치에 대해서 한 번 알아봤습니다.

이 문제는 유형을 빠르게 파악하는게 중요하네요. return 해야하는 값을 어떤 범위안에서 줄여나갈 수 있을까? 라는 아이디어로 접근해보시면 그래도 실마리를 찾을 수 있지 않을까 싶습니다.

 

그럼 이만!