프로그래머스 - 입국심사 파이썬

문제 

프로그래머스

 

접근 

제한사항

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

제한사항의 n과 times가 크기 때문에 이진탐색을 사용해야함을 알 수 있다 

나의 그림실력 ㅎㅎ..

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

이 부분이 조금 까다로울거라고 생각이 들었는데 이분탐색으로 최적의 시간(가장 시간이 적게 걸리는 심사대에서 최대한 많은 심사)을 구하면 해결이 된다

 

코드 

def solution(n, times):
    left, right = 1, max(times) * n  # 이분 탐색을 위한 범위 설정. 최솟값은 1, 최댓값은 가장 오래 걸리는 심사관이 모두 심사하는 경우
    answer = right  # 최종 결과값을 저장할 변수. 초기에는 최댓값으로 설정

    while left <= right:  # 이분 탐색을 진행하는 반복문. 왼쪽 범위가 오른쪽 범위를 넘어갈 때까지 반복
        mid = (left + right) // 2  # 현재 범위의 중간값
        people = sum(mid // time for time in times)  # 중간값을 각 심사관이 걸리는 시간으로 나누어 심사를 마친 사람의 수를 계산

        if people >= n:  # 심사를 마친 사람의 수가 n 이상인 경우
            answer = min(answer, mid)  # 현재까지의 최소 시간을 갱신
            right = mid - 1  # 오른쪽 범위를 줄여서 더 작은 시간을 탐색
        else:
            left = mid + 1  # 왼쪽 범위를 늘려서 더 큰 시간을 탐색

    return answer  # 최소 시간을 반환