문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
심사관은 1명 이상 100,000명 이하입니다.
문제풀이
문제를 처음 보았을 때 선형적으로 그대로 생각해서 구현할까 생각을 했었지만 구현 자체가 어려울 것 같아 패스하고 시간으로 for문을 순회하며 찾아볼까 하다가 범위가 너무 많아 이것도 패스...
그래서 효율적인 순회를 생각하다가 이분 탐색을 사용하게 되었다.
개인적으로 제한 사항을 가볍게 읽고 지나갔었는데 어떤 분의 블로그를 보다가 제한 사항 부분도 코테에서 힌트로 작용할 수 있다는 글을 보았다.
정리하자면, 제한 사항에서 나오는 범위가 크다는 것은 단순하지만 효율적인 알고리즘을 사용해야할 확률이 높고, 범위가 작다면 구현이 어렵고 시간복잡도가 복잡해도 괜찮다는 의미일 확률이 높다고 했다.
이번 문제의 경우 범위가 아주 크다.. 그래서 단순하지만 효율적인 알고리즘을 사용하는 것이 좋은 선택인듯 하다.
다소 뜬금 없지만 이 문제의 경우 이분 탐색을 사용하기 적절한 문제이다. 왜냐하면, 1. 범위가 커서 효율적인 탐색이 필요하고 2. 정렬 되어있는 배열이 있어야한다. 는 조건을 모두 만족하기 때문이다.
(개인적으로 그리디의 상위호환 st..)
그렇게 구현한 코드는
def solution(n, times):
answer = 0
times = sorted(times)
max_time = times[-1] * n // 최대한 많이 걸리는 시간.
min_time = 1 // 시간은 0이 없다 ㅎ..
while min_time <= max_time :
mid_time = (min_time + max_time)//2
chk_num = 0 // 심사관들이 체크할 수 있는 인원들
//mid_time동안 각각의 심사관이 체크할 수 있는 인원들
for i in range(len(times)):
chk_num += mid_time//times[i]
if chk_num >= n:
max_time = mid_time - 1
answer = mid_time
else:
min_time = mid_time + 1
return answer