입국심사

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

입국심사
이분탐색 
1833명 완료

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

이분(이진)탐색은 최대값, 최소값, 중간값을 두고.. 
찾는 값이 중간값보다 낮으면
최대값을 '중간값-1'으로 낮추고 

찾는 값이 중간값보다 높으면
최소값을 '중간값+1'으로 올려주면서 

숫자를 찾아가는 방식이다.

예전에 블로그에 정리한 적 있다. 
https://comdoc.tistory.com/entry/32-%EC%9D%B4%EC%A7%84-%EA%B2%80%EC%83%89Binary-Search

32. 이진 검색(Binary Search), 파이썬

 

이분탐색에 적합한 형태로 생각을 전환해야 한다.  
(파라메트릭 서치)

https://sarah950716.tistory.com/16

[이분탐색] 파라메트릭 서치(개념)

 

중간 값을 기준으로 생각해 보자.

최대 시간: 제일 느린 데스크에서 걸리는 시간 * 사람 수
최소 시간: 0 (승객이 0명일 때도 생각해야) 

중간 값(시간)을 계산한 뒤 
'시간(중간 값) 내에 승객이 모두 통과 가능한가.'

통과한 사람이 n 보다 작으면 절대 답이 될 수 없고... 
n보다 작지 않은 마지막 mid가 답이 된다..

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

테스트 1 〉	통과 (0.02ms, 10.2MB)
테스트 2 〉	통과 (0.11ms, 10.2MB)
테스트 3 〉	통과 (3.82ms, 10.3MB)
테스트 4 〉	통과 (283.64ms, 14.2MB)
테스트 5 〉	통과 (447.40ms, 14.2MB)
테스트 6 〉	통과 (272.12ms, 14.3MB)
테스트 7 〉	통과 (528.38ms, 14.3MB)
테스트 8 〉	통과 (538.91ms, 14.3MB)
테스트 9 〉	통과 (0.10ms, 10.2MB)

좀 더 줄이자면... 

def solution(n, times):
    left, right = 1, max(times) * n
    while left < right:
        mid = (left + right) // 2
        if sum(mid // time for time in times) < n:
            left = mid + 1
        else:
            right = mid
    return left