입국심사

문제이해
n명의 사람이 모두 입국심사를 끝내는데 걸리는 최소시간구하기
times 는 각심사관이 입국심사시 걸리는 시간의 배열

이분탐색

: 정렬된 배열의 중간값으로 비교해나가기

시간복잡도가 O(n) 에서 O(logn) 으로 줄어듬

1. 가장적게걸리는시간 1, 가장많이걸리는시간 : 최대걸리는시간 *  인원수

2. 먼저 중간시간으로 몇명이 끝낼 수 있는지 검사하고

3. 그 사람수가 전체인원수보다 크면 최소시간을 그 중간값(mid)로 하고 가장맥시멈시간을 중간값 -1 로 한다

4. mid시간동안 전체 인원이 심사를 못끝냈다면 mid시간안에는 다 못끝냈으므로 mid + 1을 최소시간으로 한다

 

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

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

n = 6
times = [7,10]
print(solution(n,times))

 

if people >= n:
    break
    
 # 없어도 성공하지만 시간줄일 수 있음