[프로그래머스] 입국심사

문제

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

풀이

이분 탐색을 활용하여 푼 풀이

이분 탐색할 범위를 지정한다.
이 범위는 심사 기간의 전체 범위이다. 이 범위 중 하나가 정답이다.
start: 0(분)
end: max(times) * n

end가 max(times) * n 는 모든 사람이 심사 기간이 가장 긴 심사위원에게 갔을 경우이다.

문제 요구 사항에는
가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.

라고 되어 있으나 휘말리면 안되는 것 같다.

이후 이분 탐색을 통해 정답을 찾는다.

해당 시간동안 심사위원별로 심사할 수 잇는 사람의 수를 구해 모두 더한다.

만약 이 값이 n(손님 수)보다 크면 범위를 왼쪽으로 옮기고 answer를 초기화한다.
작다면 정답이 될 수 없으니 범위를 오른쪽으로 옮긴다.

def solution(n, times):
    answer = 0
   
    start, end = 1, max(times) * n
      
    while start <= end:
        mid = (start + end) // 2
       
        total = 0
        for time in times:
            total += mid // time
            if total >= n:
                break
   
        if total >= n:
            end = mid - 1
            answer = mid
        else:
            start = mid + 1
           
    return answer

회고

기업 코테에서 이분 탐색이 많이 나오는 것 같아 정복하려고 시작했는데 쉽지 않다..
당분간 이분 탐색만 풀어야겠다..
파이썬 내장 라이브러리 없이 이분 탐색 문제를 쉽게 풀 수 있을 때까지 힘내보자