프로그래머스(programmers) 입국심사 python 정답[이분탐색 풀이]

프로그래머스(programmers) 입국심사 python 정답[이분탐색 풀이]

문제 링크

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

프로그래머스

문제 정답

def solution(n, times):
    # 아이디어 : 각 걸리는 시간을 각각 전체 시간을 나눠 더해서 n이 되는다
    # 동시처리
    answer = 0
    left = 0
    right =  n * max(times)    
    while left <= right:
        mid = (left+right) // 2
        current = 0
        for time in times:
            current += (mid // time)
        if current >= n :
            right =  mid-1
            answer = mid
        else:
            left = mid+1                                    
    return answer

문제 해설

일단 범위가 10억이며, 심사관도 100,000 이기에 대충 1초에 10억번의 연산이 가능하다 해도 100,000초가 걸린다.
말도 안되는 범위 조건이 주어졌기 때문에,
이분탐색(파라메트릭 서치)를 사용을 떠올린다.

파라메트릭 서치 문제의 while left<=right, left, right에 mid 할당 두 가지 로직은 매우 정형적이며,
안의 if 로직만 좀 달라진다.
따라서 문제의 프레임은 암기한다.

해당 문제의 아이디어는 동시 처리이다.
mid가 전체 시간이라고 치면
times의 각 숫자로 mid를 나누면, 한 사람이 mid 시간 동안 처리 가능한 사람 수가 된다.
a, b, c가 각각 병렬로 처리한 사람 수를 총합하면, 해당 시간 동안 입국 심사 가능한 인원 수가 된다.

만약 current >=n이면, 시간이 충분한 것이므로, 예상 답으로 할당(answer=mid)하고 최적화를 시도한다. (mid를 줄여 총 시간을 줄인다.)
만약 current<n이면, 시간이 모자란 것이므로, 예상 답이 될 수 없으니 시간을 늘린다. (left를 늘려 총 시간을 늘린다.)