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

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

 

문제

n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.

 

모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.

입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가

매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 

return하도록 solution함수를 작성해주세요.

 

풀이

이러한 n개의 사람(또는 사물)에 순서대로 작업을 처리하고 처리하는데 걸리는 시간이 서로 다를 경우,

높은 확률로 이분법 문제입니다.

 

그럼 먼저 범위를 지정해보도록 하겠습니다. 시작(left)은 0, 가장 오래 걸릴 수 있는 값인 끝(right)은?

모든 사람들이 가장 오래 걸리는 입국심사대에서 검사를 받는 경우입니다. 따라서 left, right는 아래와 같이 정의할 수 있습니다.

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

정답 또한 이 범위 안에 존재하게 됩니다. 이제 해야 할 것은 이분법을 사용해 (left+right)//2의 시간일 때 처리할 수 있는

인원수를 구하는 것입니다.

 

입출력 예제에 나온 것처럼 times가 7,10 / n이 6일 때를 예롤 들어보겠습니다.🌹

이 때 left는 0, right는 n * max(times)인 60입니다.

그럼 처음은 (left + right) // 2인 30초가 걸렸다고 해보겠습니다.

 

한 사람은 심사하는데 7초가 걸리는 심사대는 30 // 7인 4명을 심사할 수 있습니다.

10초가 걸리는 심사대는 30 // 10인 3명을 심사할 수 있는 것을 알 수 있습니다.

총 7명을 심사할 수 있는 것이죠.

while left <= right:
	mid = (left+right) // 2
    
    people = 0 # 입국심사 받은 인원 수
    for i in times:
    	people += (mid // t)

 

여기서 저희는 30초에 7명을 심사할 수 있으니 더 적은 시간이 걸려도 모든 사람을 심사할 수 있는 것을

알 수 있습니다.

그럼 다음에 검사할 범위는 left = 0, right는 30-1인 29 -> 1 ~ 29의 범위입니다.

# 모든 사람을 처리할 수 없는 경우 -> 더 오랜 시간 필요
if people < n:
	left = mid + 1
else:
	answer = mid
    right = mid - 1

 

이를 코드로 구현하면 아래와 같습니다.

 

코드

def solution(n, times):
    answer = 0
    left, right = 0, n * max(times)
    
    while left <= right:
        mid = (left+right) // 2
        
        people = 0
        # mid 시간 동안 처리할 수 있는 사람의 수
        for t in times:
            people += (mid//t)
        
        # 모든 사람을 처리할 수 없는 경우 -> 오른쪽 영역 검사
        if people < n:
            left = mid + 1
        else:
            answer = mid
            right = mid - 1
    
    return answer