[코딩테스트] 프로그래머스 - 입국심사 (Lv.3) in Python

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는 데 걸리는 시간이 담긴 배열 times가 주어질 때,

모든 사람이 심사를 받는 데 걸리는 최소 시간을 return하세요.

 

 

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

 

 

풀이

- 입국심사에 드는 시간 중 최댓값 (최악의 경우)은 max(times) * n.

- n은 최대 1억, times[i]는 최대 1분, times의 길이는 최대 10만

- 이렇게 변수의 크기가 크기 때문에, 최대한 알고리즘 수행 속도를 줄일 수 있게 이분탐색을 도입한다.

 

- 기존 기본적인 이분탐색 문제와 다른 점은, 원하는 값이 mid와 같은 상황 - "Search 성공" -이, 꼭 우리가 원하는 답이라는 보장은 없다는 것이다.

- 그 경우보다 더 최적의 경우가 존재할 수 있기 때문.

 

- 따라서, 원하는 값이 mid와 같은 상황이 나온다 해도, 끝까지 이분탐색 루프를 돌려야 한다.

 

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

    answer = right

    while left <= right:
        mid = (left + right)//2
        count = 0

        for i in times:
            count += mid // i

        if count < n: #impossibile
            left = mid + 1
        else: # possible
            right = mid - 1
            if answer > mid:
                answer = mid


    return answer