알고리즘 기법
- 이분탐색
+ 찾는 값(걸리는 시간)을 대상으로 이분탐색 진행
설명
문제에서 비어 있는 심사대로 가서 심사를 받을 수도, 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳에서 심사를 받을 수도 있다고 설명하는데 여기에 현혹될 필요 없다.
중요한 것은 모든 사람이 심사를 받는 데 걸리는 시간을 최소로 하는 것이다.
이 문제를 푸는 방법으로 2가지를 생각했다.
첫번째로 시물레이션이다, 즉 걸리는 시간을 모르는 상태에서 직접 시도해 보며 찾아 가는 것이다.
그러나 여기엔 문제가 있다.
더 빨리 끝나는 심사대가 있을 시, 기다렸다가 그곳에서 심사를 받는 것과 그냥 비어있는 곳 아무데나 들어 가는 것 둘 중 어떤 것이 어떤 조건에서 최솟값을 구하는 데 기여하는지 알 수 없다는 것이다.
(+시간도 너무 많이 걸린다. 최대 10억명이 줄을 선다니..)
두번째로, 걸리는 시간을 하나 지정해 놓고 출발하는 것이다.
이렇게 걸리는 시간을 x라고 지정했다고 하면, x시간 동안 최대 몇명이 심사대를 통과할 수 있는지 확인한다.
times는 입국심사대의 심사관마다 심사하는 데 걸리는 시간이 담긴 배열이다.
m은 입국심사대의 총 개수다.
n은 기다리는 인원이다.
총 통과 인원 = SUM(int(x / times[i])), i = 0 ~ m-1 이다.
여기서 int(x / times[i])는 입국심사대 i에서 x시간동안 최대로 통과시킬 수 있는 인원이다.이제 두번째 방법을 푸는 방식이 다시 2가지로 나뉜다.
- 걸리는 시간의 최솟값 혹은 최댓값부터 쭉 x값을 변경해 가면서 ["총 통과 인원" == n]을 만족하는 최소 x값을 찾으면 된다.
- 최솟값, 최댓값을 지정해 놓고 이분탐색을 진행하며 ["총 통과 인원' == n]을 만족할 때마다 답을 최솟값으로 갱신하다.
1번은 선형탐색이므로 O(m) X O(n)이고 2번은 이분탐색이므로 O(m) X O(log(n))이다.
(O(m)은 총 통과 인원 = SUM(int(x / times[i])), i = 0 ~ m-1 를 구하는 데 걸리는 시간)
따라서 단순계산으로 1번은 100,000 X 1,000,000,000 번을, 2번은 100,000 X 30 번을 계산하기 때문에 당연히 2번을 선택하면 된다.
소스코드
python
# 이 문제의 key point는 2개다.
# 1. 이분탐색
# 2. 구하는 대상을 이분탐색한다.
# (구하는 값은 걸리는 시간 -> 걸리는 시간의 최솟값, 최댓값 구해서 그 사이를 이분탐색)
def find_max_time(n, times):
max_time = -1
for time in times:
if max_time == -1 or max_time < time:
max_time = time
return max_time * n
def solution(n, times):
# 문제의 답이 될 수 있는 값 중 최솟값, 최댓값 구하기
min_time = 1
max_time = find_max_time(n, times)
# 문제의 답이 최솟값이므로 갱신을 위해 최댓값으로 설정
answer = max_time
# 문제의 답(target)을 대상으로 최솟값 ~ 최댓값 사이를 이분 탐색
while (min_time <= max_time):
# 중앙 값(mid target) 구하기
target = int((min_time + max_time)/2)
# 현재 답 후보(mid target) 만큼 걸렸다고 가정했을 때,
# 각 심사관은 몇명의 인원을 통과 시켰는지 구하고 누적합(sum_n) 구하기
sum_n = 0
for time in times:
sum_n += int(target / time)
# 누적합(sum_n)과 원래의 인원(n)을 비교
if sum_n >= n:
if answer > target:
answer = target
max_time = target - 1
elif sum_n < n:
min_time = target + 1
return answercpp
#include <string>
#include <vector>
using namespace std;
long long solution(int n, vector<int> times) {
long long min_time = 1;
long long max_time = 0;
for (vector<int>::iterator it = times.begin(); it != times.end(); it++) {
if (max_time < *it)
max_time = *it;
}
max_time *= n;
long long answer = max_time;
while (min_time <= max_time) {
long long target_time = (min_time + max_time) / 2;
long long sum_n = 0;
for (int time : times)
sum_n += (target_time / time);
if (sum_n >= n) {
if (answer > target_time)
answer = target_time;
max_time = target_time - 1;
}
else
min_time = target_time + 1;
}
return answer;
}느낀점
이분탐색을 쓰면 될 거 같은데 걸리는 시간(찾는 값)을 대상으로 탐색한다는 생각을 하는 데까지 오래 걸렸다.
역시 물꼬를 트는 게 제일 어렵다...
