[프로그래머스] 입국심사 - python

입국심사

문제 설명

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

제한사항

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

풀이

제한 사항을 보고 이진탐색 문제임을 알 수 있었지만 어디를 이진 탐색해야할지 아이디어가 떠오르지 않았다. 그러다 질문 게시판에서 힌트를 얻었다. 문제의 목표는 심사 받는데 걸리는 시간의 최솟값이다. 그러므로 총 걸리는 시간을 이진 탐색해야한다.

1. left = 0, right = 최악의 시간으로 정한다.
2. 이진 탐색을 시작하면서 mid의 시간 안에 처리할 수 있는 사람의 수를 구한다.
3. 동시에 처리하므로 mid를 각 시간으로 나눈 몫을 더하면 된다.
4. 처리할 수 있는 사람이 n보다 클 경우 시간을 줄여서 탐색해본다
5. 처리할 수 있는 사람이 n보다 작을 경우 시간을 늘려서 탐색해본다.
6. mid 시간에서 처리할 수 있는 사람의 수가 n과 같다면 탐색을 종료한다.

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

이진탐색문제는 문제의 목표를 찾고 그것을 mid 값으로 두면 되는 것 같다.