문제

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

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

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

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

제한 사항

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

입출력 예시

n=6, times = [7, 10] 인 경우
가장 첫 두 사람은 바로 심사를 받으러 갑니다.

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

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

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

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

풀이

이분탐색으로 분류되어있어서 의아했다.. 이분탐색을 어디다가 적용하라는 건지 전~혀 감이 오지 않았다... 그래서 결국 구글링을 했고, 좀 생각을 해서 이분탐색을 적용하는 문제였음을 알게 되었다.

아이디어

[핵심 아이디어]

• '시간의 범위'에 대해서 이분탐색을 진행한다.
• 특정 시간 내에 통과할 수 있는 사람 수를 구하고, 이를 n과 비교하는 것이 핵심.

우리가 구하는 것은 "n명의 사람을 times의 심사대에 통과시킬 때 걸리는 최소 시간"이다.
그러면 최대 시간은 얼마일까? times의 심사대 중 가장 시간이 오래 걸리는 심사대에만 통과시키는 경우이다. 가장 오래 걸리는 심사 시간을 maxTime이라고 하면 총 maxTime * n분이 걸릴 것이다.
최소 시간은 우리가 구해야 하는거고, 아직 모르니까 1분이라고 하자.

이분탐색에서 필요한 개념인 "최대"와 "최소"가 모두 정해졌다. 남은 건 이분탐색 알고리즘을 적용하는 일 뿐이다. (+약간의 생각)

그러면, 이분탐색 알고리즘대로 mid값을 잡아보자. 입출력 예시의 경우에는 left=1, right=60이 되겠다. 그렇다면 mid는 30이 될 것이다.

mid를 구해서 어쩔거냐..? 우리는 총 n명의 사람들을 모두 통과시켜야 한다는 것을 잊으면 안 된다. mid 시간동안 총 몇 명을 통과시킬 수 있는지 생각해보자. 1번 심사대는 심사에 7분이 걸리므로 30분동안 4명을 통과시킬 수 있을 것이며, 2번 심사대는 10분이 걸리므로 30분동안 3명을 통과시킬 수 있을 것이다. 그러면 30분동안은 총 7명을 통과시킬 수 있다.
우리가 통과시킬 사람들은 6명인데, 7명까지 통과시킬 수 있을 정도의 시간이면 더 줄여야한다. 따라서, right값을 60에서 mid-1인 29로 변경한다.

그럼 이제 다시 mid값이 15로 변한다. 15분동안에는 총 몇명을 통과시킬 수 있는가? 1번 심사대에서 2명, 2번 심사대에서 1명을 통과시킬 수 있다. 우리는 총 6명을 통과시켜야 하는데 턱없이 부족하다! 따라서 우리는 left값을 mid+1로 업데이트한다.

그럼 이제 다시 mid값이 22로 변한다. 22분동안에는 총 몇명을 통과시킬 수 있는가? 1번 심사대에서 3명, 2번 심사대에서 2명을 통과시킬 수 있다. 5명 < 6명이므로 또 부족하다! 그러면 또 left를 mid+1로 업데이트 한다....

이런 식으로 left와 right를 <n명을 통과시키는 데 걸리는 총 시간>을 기준으로 잡아서 업데이트를 해나가고, 최소 시간을 리턴하라고 했으니 left를 리턴해주면 된다.

코드

//n명이 모두 심사를 받을 수 있다는 조건을 "만족하는" 시간 중 최솟값 찾기
function solution(n, times) {
    //최소소요시간: 1, 최대소요시간: times최대값 * 사람수
    times.sort((a, b) => a - b);
    let left = 1, right = n * times[times.length - 1];
    
    let estimateCount = 0;
    let mid = Math.floor((left + right) / 2);
    while(left <= right) {
        //mid라는 시간에는 총 몇 명이 검사받을 수 있을까?
        times.forEach(time => {
            estimateCount += Math.floor(mid / time);
        });
        
        //n명 이상의 사람들이 심사를 받을 수 있다면, 시간의 최대값을 줄이자.
        if(estimateCount >= n) right = mid - 1;
        //n명이 모두 검사를 받지 못한다면, 시간의 최솟값을 늘리자.
        if(estimateCount < n) left = mid + 1;
        
        mid = Math.floor((left + right) / 2);
        estimateCount = 0;
    }
    
    return left;
}

파이썬 코드

def solution(n, times):
    max_cost = max(times)
    left, right = 1, n * max_cost
    
    while left <= right:
        mid = (left + right) // 2
        sum = 0
        for t in times:
            sum += (mid // t)
        if sum >= n:
            right = mid - 1
        else:
            left = mid + 1
    
    return left