[프로그래머스] 입국심사 (이분탐색)

📕 문제

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

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

 

💡 풀이법

1. 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하라고 했기 때문에 입국심사에 걸릴수 있는 시간의 범위가 굉장히 커진다. 그래서 이분탐색을 이용해야 한다.

2. 범위는 1부터 Max(times)*N이 된다.

3. 반으로 나누면서 그 시간안에 모든 사람이 입국심사가 가능한지를 검사해야 한다.

4. 예를 들어 총 30분이고 입국 심사에 걸리는 시간이 7, 10분이라면 

30 // 7 = 4 , 30 // 10 = 3 해서 총 7+3 = 10명이 30분동안 입국심사를 할 수 있게 된다.

5. 만약 이 사람수가 현재수보다 많다면 오른쪽 범위를 좁혀주고, 적다면 왼쪽 범위를 키워준다.

( 하지만 사람수가 딱 맞아떨어지지 않을 수도 있다. 적어도 n명이 입국심사를 해야 하는 것이기 때문에 크거나 같을때 answer를 mid로 변경해준다.)

 

def solution(n, times):
    answer = 0
    left = 1
    right = n * max(times)
    
    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        
        for time in times:
            cnt += mid // time

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