[프로그래머스 Lv.3] 입국심사 (Python)

문제 링크: https://school.programmers.co.kr/learn/courses/30/lessons/43238

프로그래머스

풀이

전형적인 이진탐색 문제이다. 현재 시간으로 모든 사람의 입국 심사를 진행할 수 있으면 상한선을 현재 시간으로 조절하고, 만약 현재 시간으로 모든 사람의 입국 심사를 진행할 수 없다면 하한선을 현재 시간 + 1로 조절한다. 이런 과정을 하한선이 상한선과 동일하거나 더 커진 순간까지 반복하면 이 값을 구할 수 있다.

 def solution(n, times):
    start = 1 # 하한선
    end = max(times) * n # 가장 오랜 시간이 걸리는 심사관에게 모든 인원이 심사를 받는 경우가 상한선

    def check(time): # 현재 시간 안에 통과할 수 있는지 확인하는 메서드
        total = 0
        
        for i in times:
            total += time // i
        
        if total >= n:
            return True
        return False
    
    while start < end: # 하한선이 상한선을 넘어가지 않는 경우 이진 탐색을 무한 반복
        mid = (start + end) // 2

        if check(mid): # 통과한다면
            end = mid # 상한선 조정
        else: # 통과 못하면
            start = mid + 1 # 하한선 조정 
    return start # lower bound 반환