[Python] 프로그래머스(Lv3) - 입국심사

안녕하세요 !

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

이분탐색을 이용해서 구하는 문제였습니다.

풀이

여기서 어떤 것을 이분탐색을 해야할지 생각해야 합니다.

먼저, 최악의 경우를 생각해보면 가장 오래걸리는 심사관에게 모두 배정되는 경우가 됩니다. 이 시간은 max(times) * n 이 되고 이 값을 초기 right 값으로 해줍니다.

그럼 이제 left 와 right 사이을 이분 탐색을 하면서 답을 만들 수 있는 경우 즉 cnt >= n 이 되는 경우를 구해줍니다. right 를 mid - 1로 갱신해주면서 최소값을 구해주는 겁니다.
cnt < n 인 경우는 답이 만들어지지 않는 경우로 left(하한선)를 하나씩 늘려줍니다.

def binarySearch(left, right, n, times):
    answer = -1
    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        for time in times:
            cnt += mid // time
            if cnt >= n:
                answer = mid
                right = mid - 1
                break
            
        if cnt < n:
            left = mid + 1
            
    return answer

def solution(n, times):
    left = 0
    right = max(times) * n
    answer = binarySearch(left, right, n, times)
    
    return answer