[프로그래머스] 입국심사 문제 풀이

 


1. 문제

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

2. 풀이

  • 처음에 이 문제를 어떻게 풀어야 될지 매우 난감해서 다른 분들의 풀이를 참조하였습니다.
  • 이진 탐색을 이용하면 쉽게 풀 수 있는 문제였습니다.
    • 이진 탐색을 이용하여 최대 가능한 시간(최소검색시간을 가진 검색원의 검색 시간 * 사람수)과 0초를 기준으로 가능한 시간을 줄여갑니다.
    • 각 탐색마다 middle 값의 시간동안 각 검색원들이 가능한 검색가능한 사람 수를 모두 더한 후 비교합니다. 가능하면 답으로 갱신, 가능하지 않으면 넘어가는 과정을 반복합니다.
def solution(n, times):
    answer = -1
    left = 0
    right = min(times) * n
    middle = -1
    times.sort()
    
    while left <= right:
        can_people = 0
        middle = (right + left) // 2 
        for t in times:
            can_people += middle // t
        
        if can_people >= n :
            answer = middle
            right = middle - 1
        else : 
            left = middle + 1
            
    return answer