[프로그래머스 | 파이썬3] 이진탐색 (2) / 입국심사

▶ 입국심사

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

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

> 이진탐색 활용

나와있는 문제보다 더 쉬운 예제를 들어보자. 

time= [2,3]

n= 3이라고 해보자

이때 탐색가능한 범위로는 3분에 3을 곱한 9분이 된다. 

[1,2,3,4,5,6,7,8,9]

- left=1, right= 9, mid= 5이다. 5이하의 수 중 2와 3의 배수로는 3개가 있다. 즉 5분이면 3명의 입국심사를 마칠 수 있다. 그러나 5는 time 수들의 배수도 아니고 끝낼 수 있는 최소 시간도 아니다. 

- 따라서 right를 mid값으로 놓고 다시 탐색한다. left=1, right=5, mid= 3이다. 3이하의 수 중 2와 3의 배수로는 2개가 있다. 입국심사를 해야하는 3보다 작으므로 이 시점에서 최소시간을 구할 수 있을 것이다. left를 mid값으로 놓아보자. 

- left= 3, right=5, mid=4이다. 4이하의 수 중 2와 3의 배수로는 3개가 있다. 즉 4는 time의 배수이자 3명의 입국심사를 마칠 수 있는 최소시간으로 정답이 된다. 

 

위의 예시를 구현한 코드는 다음과 같다. 

def solution(n, times):
	# time에서 가장 최댓값에 인원수를 곱한 값을 탐색 최대범위로 설정
    right= max(times) * n
    # 입국심사는 최소 1분이 걸리기 때문에 최소범위를 1로 초기화
    left=1
    
    while left < right:
        total=0
        mid= (left+right) //2
        
        # 기준값은 1부터 mid까지 몇명의 손님을 받을 수 있는지로 설정
        for t in times:
            total += mid // t
            
        # mid까지 받을 수 있는 손님이 n보다 크면 최대 탐색범위를 mid로 줄임
        # mid까지의 가용손님이 n과 동일한 경우에는 문제에서 요구하는 최소값이 아니기 때문에 범위 줄임
        if total >= n:
            right= mid
        # mid까지의 가용손님이 n보다 작아진 경우 mid에 1을 더한 값으로 최솟값을 구할 수 있음
        else:
            left=mid+1
            
    return left