[Programmers] Lv3. 입국심사

링크

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

문제 설명

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

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

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

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

 

제한사항

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

문제 해설

입국 심사를 기다리는 인원 n이 10만을 넘어가는 것을 보자마자 이분탐색을 떠올려야 한다.

완전 탐색으로 접근할 경우 심사관 한명이 최대의 시간으로 최대의 인원을 심사하는  최악의 경우 cost가 1,000,000,000 * 1,000,000,000이나 걸린다.

만약 이분탐색으로 한다면 최악의 경우가 약 60회의 반복(2^30 * 2^30이므로)만으로 정답이 나온다는 것을 보장한다.

 

이분탐색에서 가장 중요한 것은 이분탐색할 변수 설정, 종료조건, 정답을 판별하는 조건문, 범위 갱신 방법을 잘 설정하는 것이다.

시간의 최솟값을 알고자 하므로 시간을 기준으로 이분탐색을 진행한다.

low를 1로 설정하고 mid는 (low+high)//2로 갱신한다.

이때, 시간은 최악의 경우 1,000,000,000 * 1,000,000,000이 나오므로 high를 해당 값으로 설정한다.

 

high는 정답이 되는 범위, low는 정답이 아닌 범위+1로 설정하여 low와 high가 같아질 경우를 종료조건으로 설정한다.

 

조건문을 생각하자면, 탐색할 시간 mid에 대해서 각 times로 나눠진 몫을 더해주면 해당 시간이 됐을때 심사가 완료된 인원의 수를 구할 수 있다. 이 값이 n보다 크거나 같으면 해당 값부터는 정답의 범주에 들어간다.

 

범위를 갱신할 때, 조건문에서 참이 나왔다면 high=mid로 하고, 거짓이 나왔다면 low=mid+1로 하여 정답을 다시 탐색한다.

 

마지막으로 high=low+1일때의 경우를 살펴봐서 정당한 알고리즘인지 확인하자

high는 최악의 시간을 가정하여 초기화했으므로 언제나 참이 될 것이다.

위의 알고리즘대로 동작했을 경우, high는 조건문이 참이고, low는 참 혹은 거짓이다. 

만약 low에서 거짓이 나왔다면, low+=1이 되어 high=low가 되고 high가 정답이 된다.

만약 low가 참이라면 mid=(low+high)//2에서 mid=low가 되고 이에 따라 high=mid=low가 되고 high가 정답이 된다.

그러므로 탐색이 끝났을 때, high값을 정답으로 제출하면 된다.

def solution(n, times):
    answer = 0
    low=0
    high=1000000000*1000000000
    mid=(low+high)//2
    
    while low<high:
        cnt = 0
        for t in times:
            cnt += mid//t
        if cnt>=n:
            high = mid
            mid = (high+low)//2
        else:
            low = mid+1
            mid = (high+low)//2
        
    answer = mid
    
    
    return answer