[프로그래머스/Level 3/Python3] 입국심사

반복문을 통해서 하나하나 검사하기에는 심사관의 수와 입국심사를 기다리는 사람의 수가 너무 많다. 따라서 이분탐색을 이용한다.

 

개인적으로 나는 어떤 식으로 이분탐색을 적용해야 하는 문제인지가 어려웠는데,

가능한 총 심사 시간의 최소값 ~ 최대값 사이를 이분탐색하며 n명의 사람을 모두 심사할 수 있는 가장 짧은 시간을 탐색하는 문제라고 생각하면 된다.

입출력 예 설명은 풀이에 오히려 혼란만 주므로 참고하지 않는 것이 좋다.

 

여러 풀이들을 찾아봤지만 최대값을 지정하는 방법이 풀이마다 달랐다. 왜인지는 모르겠다...나는 내가 납득 가능한 풀이를 참고해서 최대값을 지정했다. 자세한 내용은 다음과 같다.

 

최소 : 1
각 심사관이 한 명을 심사하는데 걸리는 시간이 1분 이상 * 입국심사를 기다리는 사람은 1명 이상

최대 : n * max(times)
심사관 중 가장 심사시간이 긴 사람이 모든 사람을 심사하는 경우

 

위 최소,최대값 사이에서 이분탐색을 진행하면 문제를 풀 수 있다. 

 

def solution(n, times):
    answer = 0
    left = 1 
	#심사 시간 범위의 최소값
    right = n * max(times) 
    # 심사 시간 범위의 최대값 (입국심사를 기다리는 모든 사람 * 심사가 가장 오래 걸리는 심사관)
    
    while left <= right: #최소값이 최대값보다 작거나 같으면 반복문을 돌린다.
        mid = (left + right)//2 #현재 기준으로 삼은 심사시간
        count = 0 #심사 가능 인원
        for time in times:
            count = count + mid // time
            
            if count >= n: #모든 인원을 심사 가능해지는 시점에 반복문을 종료한다.
                break 
                
        if count >= n: 
            #mid의 심사시간동안 모든 인원을 심사할 수 있다면 
            right = mid - 1 #최대 심사 시간을 줄여서 다시 반복한다.
            answer = mid 
            # mid가 답이 될 수 있으니 answer 값을 업데이트한다.
            # 업데이트 되는 값은 반드시 이전 값보다 작으므로 따로 조건문을 더해주지 않아도 된다.
        else:
            #mid의 심사시간동안 모든 인원을 심사할 수 없었기 때문에
            left = mid +1 #최소 심사 시간을 늘려서 다시 반복한다.
            #현재 mid값은 답이 될 수 없으므로 answer 값을 업데이트 하지 않는다.
    return answer