https://school.programmers.co.kr/learn/courses/30/lessons/43238
문제 파악
입국심사를 기다리는 사람 수 n,
각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때,
모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
n이 6, times가 [7,10]이 주어졌을 떄,
28분째일때, 0번째 인덱스 심사관이 4명, 1번째 인덱스 심사관이 2명을 심사하며 총 6명이 통과된다.
어떻게 풀 수 있을까?
이 문제는 답인 시간을 늘이고 줄이면서 최적의 시간을 찾는 문제이다.
시간을 늘이면 늘일수록 심사하는 사람수가 늘어나는데, 이를 단조성이 있다고 하고,
단조성이 있을 때, 범위 안에서 정답을 빠르게 찾는 알고리즘으로는 이진 탐색 이 있다.
가장 오래 시간이 걸리는 최악의 경우를 구하고 그 시간에 반부터 하여 좌우를 탐색하여 이진 탐색으로 최적의 시간을 찾아야 한다.
해답 및 풀이
# n = 6 , times = [7,10]
def solution(n, times):
# 탐색 범위 설정
left = 1 # 최소 시간 : 1분
right = max(times) * n # 최대 시간 : 가장 느린 심사관이 모든 사람을 다 처리하는 경우
anwer = right # 가능한 시간 중 최소값을 저장할 변수
while left <= right:
mid = (left + right) // 2 # 현재 검사할 시간
total = 0 # mid시간 동안 각 심사관이 처리할 수 있는 사람수의 합
for t in times:
total += mid // t
if total >= n: # n명을 넘으면 계산할 필요가 없음
break
if total >= n :
answer = mid
right = mid - 1
else:
left = mid + 1
return answer흐름 예시
| 단계 | left | right | mid | 처리 가능 인원 | 판단 | 결과 |
|---|---|---|---|---|---|---|
| 1 | 1 | 60 | 30 | 7 | 가능 | right=29 |
| 2 | 1 | 29 | 15 | 3 | 불가능 | left=16 |
| 3 | 16 | 29 | 22 | 5 | 불가능 | left=23 |
| 4 | 23 | 29 | 26 | 5 | 불가능 | left=27 |
| 5 | 27 | 29 | 28 | 6 | 가능 | right=27 |
| 6 | 27 | 27 | 27 | 5 | 불가능 | left=28 |
mid값을 answer에 저장해놓고 더 최적의 답이 있지 않을까? 하며 mid를 토막내며 mid값을 찾는 이진 탐색의 문제였다.
이진 탐색을 리마인드 할 수 있었다.
To make it count