문제
n명이 입국심사를 하려고 합니다. 입력으로 심사관이 한명을 심사하는데 걸리는 시간이 주어집니다. 모든 사람이 심사를 받는데 걸리는 시간을 구하는 문제입니다.
풀이
완전탐색
10억이라는 최대입력값때문에 완전탐색을 할까말까 고민했지만 일단 한번 해보았습니다. 각각의 사람이 심사를 받는 전과정에 대해서 구현한것인데요. heapq를 사용해서 모든 연산을 해보았습니다. 처음에 heapq에 time의 모든 시간과 각 시간의 인덱스를 집어넣습니다. 다음으로 반복문을 n번 수행하면서 heapq의 루트를 뽑고 루트가 가지고 있는 값(누적)과 시간의 인덱스로 time값(심사위원이 한사람을 심사하는데 걸리는 시간)을 구하고 더해 다시 집어넣습니다. heapq의 루트값은 매 반복문 마다 심사위원 중 가장 빨리 종료한 시간을 가지게 됩니다. 그림으로 나타내면 다음과 같습니다.
하지만 이 방법은 시간 초과가 납니다. 삽입/삭제가 N번씩 일어나고 삽입/삭제 각각 logN이므로 NlogN의 시간복잡도를 가지게 됩니다. N이 최대 10억이므로 이 방법은 시간초과를 하게됩니다.
이분탐색
사실 이 문제를 보고 이분탐색으로 풀어야겠다는 생각은 들지않았습니다. 문제를 풀다가 도저히 모르겠어서 알고리즘 카테고리를 보았는데 이분탐색으로 풀어야한다는 힌트를 얻을 수 있었습니다.
우리가 원하는 정답은 1초와 times의 max값 X N 사이에 위치합니다.
times의 max값이란 가장 느린 심사위원이 한명을 심사하는데 걸리는 시간입니다. 가장 느린 심사위원 혼자서 N명을 모두 심사하는데 걸리는 시간은 N명을 모두 심사하는 시간중 가장 오래걸리는 시간입니다. 이 범위를 가지고 다음과 같이 이분탐색을 할것입니다.
먼저 범위의 mid값을 각 time으로 모두 나누고 각 나눈값들을 다 저장합니다. 그 값은 당연히 심사를 받은 사람의 인원수겠죠. 예를 들어 문제에서의 예제는 1초 ~ 120초 범위를 가지고 각 심사위원은 7초, 10초의 심사 시간을 각각 가집니다. 또한 6명을 심사하는 최소시간을 구하는것이 목표입니다.
해당 범위의 mid값인 60초가 주어진다면 심사관0번은 8명, 심사관1번은 6명을 심사할수있습니다. 따라서 60초가 주어진다면 총 14명을 심사할수있는것입니다. 시간이 너무 깁니다. 후보군을 축소할수있습니다. 저는 60초를 후보군에 포함시켰습니다. 60초는 최적의 답은 아니여도 답의 후보군에는 존재할수있기때문입니다. 이제 정답의 후보 범위는 1초 ~ 60초 입니다.
같은 과정을 진행합니다. 진행하다보면 범위가 1초~30초일때가 존재합니다. 이때의 mid는 15초이며 심사관0은 2명을 심사관1은 1명을 심사하며 총 심사하는 사람의 수는 3명이 되게 됩니다. 15초는 후보군에도 들지 못한다는 사실을 알수있습니다. 앞에서 보았던 60초는 6명을 넘겨서 심사했지만 정답의 후보군에는 들수있습니다. 하지만 15초는 6명을 심사하지도 못했습니다. 따라서 후보군에서 제외합니다. 이제 범위는 16~30초가 됩니다. 이렇게 범위를 좁혀나가다보면 최종적으로 범위가 하나의 값에서 만날때가 생깁니다. 그 값이 곧 답입니다. 즉 이 모든 과정은 아래의 그림과 같이 이루어집니다.
코드
'''
Created by jun on 21/05/22
'''
def solution(n, times):
answer = 0
min_time = 1
max_time = max(times)*n
left = min_time
right = max_time
while left < right:
mid = (left + right) // 2
complete_person_n = 0
for time in times:
complete_person_n += mid //time
if complete_person_n >= n:
right = mid
else:
left = mid + 1
answer = left
return answer
새로 알게된 사실
이분탐색의 새로운 유형을 익혔습니다.
