[프로그래머스] 입국심사

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

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

 

 

< 문제설명>

입국심사를 기다리는 사람 수 n, 각 심사관이 한명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어진다.

모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 리턴하라.

입국 심사는 동시에 한 명만 가능하고, 빨리 끝나는 심사대로 가서 심사를 받을 수 있음.

 

 

< 문제 이해 >

문제의 제한사항이 위와 같았다.

짧은 예시만 보고 처음에는 모든 경우의 수를 구해서 최솟값을 구하면 될 것이라고 생각했다.

하지만 입국심사를 기다리는 사람이 1,000,000,000명이고 심사관이 100,000명이라면

모든 경우의 수를 구하는 것이 아주 어려울 것이라고 생각했다.

 

그렇다면 이분탐색! (문제 분류가 이분탐색ㅎㅎㅎ)

보통 이런문제를 이분탐색으로 푸는 경우에는

걸리는 시간을 이분탐색한다.

이때, 조건은 시간으로 할 수 없기 때문에 기준 시간동안 입국심사를 받을 수 있는 사람의 수로 한다.

 

 

< 문제 풀이 >

def solution(n, times):
    answer = 0
    left = 1			# 입국심사에 걸리는 시간 최소 1분
    right = max(times)*n	# 최대로 걸리는 시간
    
    while left <= right:
        mid = (left + right) // 2
        cnt = 0
        
        for time in times:		# 한 상담원이 몇 명을 맡을 수 있는지 계산
            cnt += mid // time
            if cnt >= n : break		# n보다 크거나 같아지면 그만
            
        if cnt >= n :			# n보다 크면 mid가 작아져야함.
            answer = mid
            right = mid - 1
        else :				# n보다 작으면 mid가 커져야함.
            left = mid + 1
    
    return answer