[python] 43238 입국심사

1. 문제

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

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

2. 접근 방법

이분탐색인데요~!

(이분탐색인 이유 1. 이분탐색 탭에 위치한 문제다 2. 입국심사를 기다리는 사람이 10억명이고, 심사관이 심사하는 데 걸리는 시간이 최대 1억이고, 심사관이 최대 10만명 이하이기 때문에 이분탐색입니다.)

 

여튼 그래서 심사에 걸리는 총 시간을 기준으로 이분탐색을 해주면 됩니다.

 

상당히 생각하기 까다로운 문제예욧 흥!

 

사실 이분탐색은 이분탐색이라는 것을 깨닫기까지가 정말 어려운데, 이 문제는 알고봐도 어떻게 접근해야할 지 엄두가 안났습니다

 

저만 그런가요호~!

 

여튼 최대 심사시간을 최댓값으로 해서 중간 값으로 총 몇명 심사가 가능한지 확인합니다.

만약 주어진 n보다 큰 값이 나온다면 값을 더 줄여도 되기 때문에 right값을 mid -1로 해서 이분탐색을 진행하고,

주어진 n보다 작은 값이 나온다면 값을 늘려야하기 때문에 left값을 mid+1로 해서 이분탐색을 진행합니다.

일반적인 이분탐색은 원하는 값을 찾으면 return하지만, 

이 문제의 경우에는 최솟값을 찾아야하기 때문에 원하는 값을 찾더라도 return하지 않고 answer만 갱신해서 나아가야합니다.

3. 코드

Python

def solution(n, times):
    left = 0
    right = max(times) * n
    answer = right

    while left <= right:
        mid = (left + right) // 2
        temp = sum([mid // i for i in times])
        if temp >= n:
            right = mid - 1
            answer = min(mid, answer)
        else:
            left = mid + 1
    return answer

4. 마치며

이분탐색은 어렵지 않지만 문제에 적용하기 까다로운거 같아여 흥