[Programmers/Level 3/Python] 입국심사

Programmers(프로그래머스) 레벨 3 입국심사

코딩테스트 연습 - 입국심사

문제 설명

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.

ex)
n = 6,  times = [7, 10]
=> 28

풀이

시간을 하나씩 증가시키면서 매번 확인하기에는 시간이 너무 오래 걸린다.
이분 탐색(Binary Search)을 활용하여 빠르게 해결할 수 있다.

알고리즘 처리 단계는 다음과 같다.

(1) 최소(left)는 0시간, 최대(right)는 가장 심사 시간이 긴 심사대 하나가 모든 사람을 처리하는 경우로, max(times)*n으로 시작한다. answer도 최대 시간으로 초기화한다.
(2) 임의의 총 심사 시간을 최소 시간과 최대 시간의 중간값(mid)로 지정한다.
(3) 각 심사대가 mid 시간만큼 동안에 처리할 수 있는 최대 심사 인원 수를 구해 누적한다. 이것은 mid 시간 동안 총 심사할 수 있는 인원의 수가 된다.
(4) 처리할 수 있는 심사 인원 수가 목표 인원 수 n보다 작으면 left를 mid+1로 정정한다.(처리한 심사 인원 수를 늘리기 위함)
(5) 처리할 수 있는 심사 인원 수가 n보다 같거나 크면 right를 mid-1로 정정한다.(총 심사 시간을 줄이기 위함)
    이때, mid가, 저장해둔 심사 시간 answer보다 짧은 시간이면 answer에 저장해둔다.
(6) answer를 반환한다.

위 단계를 Python 코드로 구현하면 다음과 같다.

def solution(n, times):
    left = 0
    answer = right = max(times) * n  # 심사 처리 최대 시간 == 가장 오래걸리는 심사대가 모든 사람을 처리

    while left <= right:
        task_sum = 0  # 심사 처리 수
        mid = (left + right) // 2  # 임의의 총 심사 시간

        # 각 심사대가 mid만큼의 시간이 주어졌을 때, 처리할 수 있는 최대 심사 인원 수
        # 모두 합해서 목표 심사 인원 n과 비교할 것임
        for time in times:
            task_sum += mid//time

        # mid 시간동안 처리한 심사 인원 수가 n보다 작으면 left 정정
        if task_sum < n:
            left = mid+1
        else:
            right = mid-1
            if mid <= answer:  # 이전에 저장한 총 심사 시간보다 작은 심사 시간인 경우 다시 저장
                answer = mid
                
    return answer