Algorithms / Programmers / 입국심사

링크

https://programmers.co.kr/learn/courses/30/lessons/43238

풀이

• binary search문제.
• 탐색 전체를 하는데 가장 짧은시간이 걸리는 경우: left = 가장 빠른 심사관 혼자 1명 검사
• 탐색 전체를 하는데 가장 오랜시간이 걸리는 경우: right = 가장 느린 심사관 혼자 n명 검사
• left and right값을 점차 줄여가며 left가 right을 넘어가는 순간 종료
• 반복

코드

def solution(n, times):
    answer = 0
    left = min(times)
    right = max(times)*n
    # Looping is done when left is greater than right.
    # It means mid=avg(min+max) has been decided.
    # Therefore, no more searching.
    while left<=right:
        mid = (left+right) // 2
        est = 0
        for time in times:
            est += mid//time
            if est>=n:
                # temporary answer, not done yet.
                answer = mid
                right = mid - 1
                break
        # at the end of ONE looping, 
        # but estimated people is still less than var n.
        if est<n:
            left = mid + 1
    return answer