📌 문제 링크
문제 접근
처음에 문제를 읽어내려가면서, 그리디 알고리즘과 다이나믹 프로그래밍을 떠올렸다. 하지만, 제한사항을 읽고 이진탐색 문제라는 것을 깨달아 버렸다.
Input 조건이 10^9 (10억) 이상이라면, O(N) 이상의 알고리즘을 작성했을시 효율성 테스트를 통과하지 못한다. 그래서 O(log N)의 복잡도를 가지는 이진탐색을 사용해야 하는 것이다.
이진탐색 적용
✔🙄 그럼 이진탐색을 어떻게 적용할까유
결국 문제에서 요구하는 것은 "모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요." 이다.
"심사를 받는데 걸리는 시간"을 mid로 설정한 뒤 left와 right를 와리가리 쳐야한다는 것이다.
left는 1로 설정하고, right 설정에 고민을 해본다.
🔥 예를 들어, n = 20, times = [2,3,4,10] 이라고 가정해보자. 제일 일 처리가 늦는 사람은 10의 시간이 걸린다. 무슨 방식으로 분배를 해서 일을 하더라도, 이 사람 혼자 일 다 시키는것보다는 빠를 것이다. 그래서 right는 10*20 = 200 으로 결계를 칠 수 있게 된다.
✔🙄 탐색 조건
문제의 input 'n'은 입국심사를 기다리는 사람의 수, 'times'는 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열이다.mid(심사받는데 걸리는 시간)의 최솟값을 구해야한다. 어떻게 풀어나가야 할까.
mid의 시간이 주어졌을 때, 그 시간안에 총 몇 명의 사람들을 처리해줄 수 있는지를 구해서 result에 담는다. result가 n보다 클 경우, 이 시간 mid는 n명의 사람을 심사하는데 충분히 크다는 의미 이므로, right를 mid-1로 재설정하여 탐색을 진행한다.
🔥 위에서 들었던 예시를 사용해보자.
left = 1, right = 200, mid = 100 이 된다.
2의 시간이 걸리는 사람은 100분 동안 100 // 2 = 50 명을 처리 할 수 있다.
3의 시간이 걸리는 사람은 100분 동안 100 // 3 = 33 명을 처리 할 수 있다.
4의 시간이 걸리는 사람은 100분 동안 100 // 4 = 25 명을 처리 할 수 있다.
10의 시간이 걸리는 사람은 100분 동안 100 // 10 = 10 명을 처리 할 수 있다.따라서 mid = 100 일 경우, result = 50 + 33 + 25 + 10 = 118 이 된다.
n은 20 이었는데 118 은 너무 넘쳐난다. 따라서 right = mid - 1로 설정하고 재귀적으로 알고리즘을 수행한다.
소스 코드 (Python)
<def solution(n, times): left = 1; right = max(times) * n while left <= right: mid = (left + right) // 2; result = 0 for time in times : result += mid // time if result >= n : right = mid - 1 else : left = mid + 1 return left
