모든 사람이 심사를 받는데 걸리는 최소 시간을 구하는 문제이다.
문제해결 전략
처음에는 사람 한명한명을 최소 시간을 갖고 있는 심사관에게 배치하려 하였다.
하지만 사람의 수가 최대 10억명이고 심사관의 수가 최대 10만명이므로 굉장히 큰 반복횟수가 필요하므로 한명씩 하면 안됐다.
우선 이 문제가 이분탐색 카테고리 이므로 이분탐색을 어떻게 적용할 수 있을까 생각해 보았다.
이분탐색이란 정렬된 데이터에서 특정 값을 찾는 탐색 방법이다.
이분탐색을 적용하기 위해서는 찾아야 하는 값과 정렬된 데이터가 존재해야 한다.
우선 찾아야 할 값을 어떤것으로 선정해야 하는지 고민해 보았다.
문제에서 요구하는 답은 모든 사람을 다 처리할 수 있는 최소 시간이지만 알려진 값은 사람의 수 뿐이다.
따라서 특정 시간동안 모든 사람을 처리할 수 있는지 확인하여야 한다. 즉, 현재 확인하고자 하는 시간이 t라면 t분 동안 각 심사관이 처리할 수 있는 사람수의 총합이 비교 대상이 되고, 타겟값은 처리해야 할 사람의 수가 된다.
다음으로 정렬된 데이터가 무엇일까 생각해 본다.
시간값을 비교하므로 정렬된 데이터 역시 시간과 관련된 값임을 알 수 있다.
시간의 최솟값을 1으로 한다.
최댓값은 가장 느린 심사관이 다 맡는 경우 이므로 가장느린심사시간x사람 수 가 된다.
이제 0부터 최대값 까지 이분탐색을 진행한다.
정리하자면 다음과 같다.
느낀점
이분탐색 개념은 알고 있었는데 이런식의 문제로 나오니까 어떻게 적용해야 하는지 막막했다.
좀 더 문제를 많이 풀어보며 알고있는 알고리즘을 어떻게 적용할 수 있을까 좀 더 고민해봐야 겠다.
코드
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
long long solution(int n, vector<int> times) {
long long answer = 0;
sort(times.begin(), times.end());
long long right = (long long)times[times.size()-1]*n;
long long left = 1;
long long mid;
while(left <= right){
mid = (right + left)/2;
long long cnt = 0;
for(int i=0;i<times.size();i++){
cnt += mid / times[i];
}
if(cnt < n){
left = mid + 1;
}else{
if(mid <= right){
answer = mid;
}
right = mid - 1;
}
}
return answer;
}
출처 : https://programmers.co.kr/learn/courses/30/lessons/43238