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

 

 

https://programmers.co.kr/learn/courses/30/lessons/43238?language=python3 

코딩테스트 연습 - 입국심사

 

시간이라는 범위 내에서 점점 범위값을 줄여나가면서 최소값을 찾아나가는 문제이다. 즉, 절대 불가능한 가장 작은 시간부터 가장 최악의 시간이라는 범위 내에서 해결 가능한 시간 범위를 찾고 최소를 찾는 것이다. 문제의 입출력 예를 읽고 이게 왜 이분탐색인지 받아들이기 어려웠는데 시간의 흐름에 따라 답을 구하는 방법이 아니라 일단 모든 인원을 해결했을 때 시간의 범위를 맞춰나가는 방법으로 해결하는 문제였다.

 

코드로 작성하면 다음과 같다.

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

 

⛳️ 1. 범위 설정하기

left = 1
right = max(times) * n

먼저 범위는 이 문제에서 생각할 수 있는 시간의 범위에서 가장 크게 잡는다. 그러면 left는 절대 불가능한 가장 작은 시간 right는 가장 최악의 시간으로 설정한다. 그렇다면 left는 1, right는 입국하는 모든 사람들이 가장 심사 시간이 긴 심사대에서 심사하는 경우이다.

 

⛳️ 2. 현재 '소요된 시간'일 때 모든 인원이 심사 가능한지 확인하기

mid를 소요된 시간이라고 할 때

for time in times:
    people += mid // time
    if people >= n:
        break

(총 소요된 시간) / (각 심사대에서 소요되는 시간) = (해당 시간 동안 그 심사대에서 처리할 수 있는 인원의 수) 이다.

이 인원의 수를 모두 합쳤을 때 문제에서 요구하는 인원수보다 크다면 당연히 처리할 수 있는 범위의 시간이라는 의미이다.

여기서 문제의 조건을 해결할 수 있는 코드가 나온다. 바로 people >= n일 때 끝내는 부분이다. 모든 심사대의 경우를 처리하지 않고 일부 심사대에서만 입국 심사를 해도 모든 인원을 처리할 수 있다면 끝내는 것이다. 문제에서 '더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.' 라는 조건을 해결한다.

 

⛳️ 3. 해결 가능 시간의 범위 축소

if people >= n:
    answer = mid
    right = mid - 1
else:
    left = mid + 1

people>=n 이라면 right = mid-1로 숫자가 작은 범위로 좁힌다. 왜냐하면 현재 시간(mid)이 모든 인원을 처리하고도 남는 충분한 시간이라는 뜻이기 때문이다. 그러나 left>right가 될 경우 이 시간(mid)이 해결 가능한 최소값이 되므로 answer=mid로 저장한다.

 

만약 people<n 이라면 left=mid+1로 숫자가 더 큰 범위로 좁힌다. 왜냐하면 현재 시간(mid)이 모든 인원을 처리하기엔 부족하다는 뜻이므로 더 큰 범위의 시간을 구한다.

 

이 과정을 반복하다 left > right가 되면 범위 내 가장 작은 시간을 찾은 것이므로 answer를 반환한다.