[이분탐색] 프로그래머스 - 입국심사

문제 출처 : https://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	times	return
6	[7, 10]	28

 

문제 풀이

프로그래머스에서 이분탐색이라고 분류하긴 했지만, 가장 먼저 생각난 접근법은 역시 1부터 최대 범위(시간이 가장 오래 걸리는 심사관에게서 n명이 전부 심사받는 경우)를 부터 돌면서 모든 대기 인원이 다 빠져나갔을 때에 종료하는 알고리즘이다. 이렇게 하면 코드는 어렵지 않았지만, 실행 결과에서 테스트2까지 하고 나면 3부터는 시간 초과가 떴다.

 

다음으로 생각한 것은 힙 구조를 이용한 것이었다. 가장 최근에 푼 문제가 힙 문제여서 그랬던 것 같다. 

import heapq as hq

def solution(n, times):
    hq.heapify(times)
    index_done = 0
    answer = []
    array = []
    for time in times:
        array.append((time, time))
    hq.heapify(array)    
    while index_done < n:
        answer = hq.heappop(array)
        hq.heappush(array, (answer[1]+answer[0], answer[1]))
        index_done += 1
    return answer[0]

이렇게 힙에다가 (해당 심사관이 가장 마지막에 심사를 종료한 시간, 심사관이 심사하는데 걸리는 시간) 의 튜플 구조를 넣었다. 그렇게 되면 heappop을 이용해서 가장 일찍 심사를 종료한 심사관을 pop할 수 있고 이후에 해당 심사관이 다음 사람을 심사 종료하는 시간(현재 종료된 시간 + 1명 심사에 걸리는 시간)을 push해 넣으면 된다. 그렇게 해서 한 명 끝낼 때마다 index_done을 1씩 증가해줬고 index_done이 n과 동일해지는 시점에 프로세스를 종료해주면 된다. 

 

이렇게 하니까 1부터 최대범위까지 돌 때보다는 많은 결과를 얻을 수 있었다. 하지만, 6 ~ 10번 테스트까지는 시간 초과로 결과를 얻지 못했다. (여기서 책정된 시간은 10초였다)

 

그래서 다른 블로그를 참고하여 어떤 수들을 이분탐색해야 할 지 힌트를 얻었다.

def solution(n, times):
    left, right = 0, max(times)*n
    
    while left < right:
        mid = (left + right) // 2
        total = 0
        for time in times:
            total += mid // time    #각 심사관이 심사한 사람 수의 합
        if total >= n:
            right = mid
        else:
            left = mid + 1
    return left

이진탐색을 실시할 범위는 1부터 max(times) * n 까지로, 심사 시간이 가장 긴 심사관 혼자 n명을 전부 심사할 때의 시간과 같다. 선정된 mid값에 대해서 mid // time (times의 각 원소들) 을 이용해서 각 심사관마다 몇 명을 심사했는지 그 값을 더해준다. 이렇게 되면 해당 mid 시간동안 총 몇 명의 인원을 심사했는지 알 수 있다. 이 심사 결과가 n보다 많다면 실제 걸린 시간이 mid보다 적은 것이므로 범위를 left ~ mid로 줄여준다. 반대의 경우는 범위를 mid + 1 ~ right까지로 좁혀주면 된다. 이런 과정을 정확하게 하나의 값이 나올 때까지 (left = right가 나올 때까지) 반복해준다.