[Programmers] 입국심사 (Python 풀이)

https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3 

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

이 문제는 풀어야할 문제는 쉽지만 제한사항이 엄격하여 알고리즘을 잘 사용하지 않으면 통과하기 쉽지 않습니다.

제한사항

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

---

문제 풀이의 아이디어는 다음과 같습니다.

• N명이 검사 받는데 걸리는 시간을 측정하는 것이 아니라 심사위원이 M분가 주어지면 총 몇 명의 인원을 검사하는지 이진 탐색으로 M의 범위를 줄여나가며 검사하는 것입니다. M분에 N명의 검사가 가능하다면 정답은 M이 됩니다.
• 예를 들어 심사위원의 검사시간이 각각 7분, 10분이고, M이 100초이면 100초에 검사한 인원은 100을 7로 나눈 몫 + 100을 10으로 나눈 몫으로 14+10 = 24입니다.

이진 탐색의 범위는 다음과 같습니다.

• 최소 소요 시간 : 1 (심사 시간을 계산하여 다른 값으로 설정할 수도 있지만, 알고리즘 성능에 거의 영향이 없으므로 1로 설정)
• 최대 소요 시간 : 가장 오래걸리는 심사위원의 시간 x 인원 수

소스 코드

def solution(n, times):
    # 이진 탐색으로 t초에 몇명 조사가 가능한지 범위를 줄여가며 조사한 후
    # 조사한 인원이 n인 경우의 t를 반환
    l, r = 1, max(times) * n
    while l <= r:
        mid = (l + r) // 2
        count = 0
 
        # 모든 심사관에 대해서 mid초 동안 몇명 조사했는지 count에 추가
        for t in times:
            count += mid // t
            if count == n: # 조사한 인원이 n인 경우 종료
                break
 
        # 탐색 범위 변경
        if count >= n: # 실제 조사한 인원이 더 많은 경우
            answer = mid
            r = mid -1
        elif count < n: # 실제 조사한 인원이 더 적은 경우
            l = mid + 1
 
    return answer

---