[프로그래머스] 입국심사 (level3, python)

 

 

🤔 풀이 코드

 

def check(n, times, k):
    can_enter = 0
    for t in times:
        can_enter += k // t
    return True if can_enter >= n else False

def solution(n, times):
    answer = 0
    start = 0
    end = min(times) * n
    mid = start
    
    while mid + 1 != end:
        mid = (start + end) // 2
        if check(n, times, mid):
            end = mid
        else:
            start = mid
        
    return end

 

 

🤔 문제 풀이

 

이분탐색으로 풀이해야 하는 문제입니다. 항상 이분 탐색은 시작점과 끝점을 잡는 기준과, 어떤 것을 이분탐색에 사용해야 할지 판단하는게 어렵네요.

 

이 문제에서 이분탐색의 대상은, 모든 사람이 심사를 받는데 걸리는 시간을 이분탐색의 대상으로 삼습니다.

나올 수 있는 최대 시간은, 검사관 중 가장 짧게 걸리는 검사관에서 N 명이 모두 받는 케이스가 될 수 있겠네요.

 

그래서 start와 end를 각각 0, min(times) * n으로 잡았습니다.

이분 탐색을 통해 mid를 (start + end) // 2로 설정한 후, check 함수를 통해 이분탐색의 범위의 앞을 줄일지, 뒤를 줄일지 결정합니다.

check 함수는 k 시간동안, times의 감독관들이 각각 입국 심사를 진행할 수 있는 양을 모두 더한 값을 바탕으로, 주어진 n명 이상을 채웠는지 못채웠는지에 따라 True와 False를 결정하는 함수입니다.

 

만약 채웠다면, mid 값을 좀 더 줄이기 위해 end를 mid 포지션으로 바꿉니다.

n명을 다 못 채웠다면 시간을 좀 더 늘리기 위해 start를 mid 포지션으로 바꿉니다.