문제 설명
n명이 입국심사를 위해 줄을 서서 기다리고 있습니다. 각 입국심사대에 있는 심사관마다 심사하는데 걸리는 시간은 다릅니다.
처음에 모든 심사대는 비어있습니다. 한 심사대에서는 동시에 한 명만 심사를 할 수 있습니다. 가장 앞에 서 있는 사람은 비어 있는 심사대로 가서 심사를 받을 수 있습니다. 하지만 더 빨리 끝나는 심사대가 있으면 기다렸다가 그곳으로 가서 심사를 받을 수도 있습니다.
모든 사람이 심사를 받는데 걸리는 시간을 최소로 하고 싶습니다.
입국심사를 기다리는 사람 수 n, 각 심사관이 한 명을 심사하는데 걸리는 시간이 담긴 배열 times가 매개변수로 주어질 때, 모든 사람이 심사를 받는데 걸리는 시간의 최솟값을 return 하도록 solution 함수를 작성해주세요.
제한사항
- 입국심사를 기다리는 사람은 1명 이상 1,000,000,000명 이하입니다.
- 각 심사관이 한 명을 심사하는데 걸리는 시간은 1분 이상 1,000,000,000분 이하입니다.
- 심사관은 1명 이상 100,000명 이하입니다.
입출력 예
| N | time | return |
| 6 | [7, 10] | 28 |
입출력 예 설명
가장 첫 두 사람은 바로 심사를 받으러 갑니다.
7분이 되었을 때, 첫 번째 심사대가 비고 3번째 사람이 심사를 받습니다.
10분이 되었을 때, 두 번째 심사대가 비고 4번째 사람이 심사를 받습니다.
14분이 되었을 때, 첫 번째 심사대가 비고 5번째 사람이 심사를 받습니다.
20분이 되었을 때, 두 번째 심사대가 비지만 6번째 사람이 그곳에서 심사를 받지 않고 1분을 더 기다린 후에 첫 번째 심사대에서 심사를 받으면 28분에 모든 사람의 심사가 끝납니다.
이분탐색은 O(log n)의 시간복잡도를 가진 아주 짧은시간내에 값을 찾는 탐색법이다.
우선 간단하게 말하자면 최소 값과 최대 값의 중간값과 찾는 값을 비교하여 비교대상 수들의 절반씩 없애며 탐색하는 방법이다.
하지만 이것을 어떻게 적용하는것이 힘든것이었다.
이해는 하였는데 이걸 여기서 쓸수 있는지가 의문이었다..
우선 최대값을 현재 심사관의 최대 소요시간을 잡았다.. 그거를 현재 심사받아야하는 인원을 곱하여 최대시간을 구하고.
0~최대시간까지가 구해진다..
여기서 의문점 : 0~최대시간 까지라면 심사관들의 공배수가 아닐수도 있는데 어떻게 하느냐
그래서 우리는 0~최대시간의 중간값으로 심사관들의 시간을 나눠
이중간값을가지고 심사관들이 최대 몇명을 처리 할수 있는지,
즉 위의 예제로 치자면 처음 최대값 60의 절반인 30의 시간이라면 : 7분 심사관은 4명, 10분심사관은 3명을 처리할수 있다.
어떻게 돌아가는지 감이오는것을 느낄것이다
우리가 찾는값은
현재시간(0~최대시간을 이분탐색하여 나온 시간)으로 심사관들이 최대 몇명을 처리할수 있는지를 구하여
처리할수 있는사람수를 최적으로 맞추는것이다.
위에서 말한것처럼 30분이면 4명/3명으로 7명처리할수 있어서 해당값에 맞긴하지만.
시간을 조금더 줄여서 우리가 원래 찾는 28분이라는 시간을 찾아내는것이다
#include <string>
#include <vector>
using namespace std;
long long solution(int n, vector<int> times) {
long long answer = 0;
long long minTime = 0;
long long maxTime = 0;
for(int time : times)
{
if(time > maxTime ) maxTime = time; // 최대 값을 찾아 저장한다
}
maxTime*= (long long) n; //최대시간은 모든인원이 현재 심사관중의 가장오래걸리는 심사관한테서만 받았을경우
answer = maxTime; //답을 모르니 일단 최대시간으로 설정.
while(minTime <= maxTime) //이분탐색 시작 ( 최소시간이 최대시간이하 일경우에만 실행)
{
long long aveTime = (minTime+ maxTime)/2; //중간값(이분탐색)
long long handlingHuman = 0; //처리인원수
for(int time : times)
{
handlingHuman+= aveTime/time; //중간값일경우 심사관들의 처리인원수를 모두 더한다.
}
//현재평균시간의 처리인원수가 입국심사인원보다 작으면 시간이 더필요하다는것 (즉, 답은아니다.)
if(handlingHuman < n)
{
minTime = aveTime+1; //최소시간을 평균값의+1 (이분탐색)
}
else //처리인원수가 입국심사인원과 같거나 많다면
{
if(aveTime < answer) // 현재 구해진 답(앞서 구해진 최대 처리인원수에서의 시간) 보다 시간이 적다면.
{
answer = aveTime;//바꿔준다. (최적의 값)
//이후 검색이 끝났을때 최적의시간을 찾지 못했을때 마지막으로 저장된값을 리턴하기 위해.
}
maxTime = aveTime-1; //최대시간을 평균값의+1 (이분탐색)
}
}
//중간값일때 처리할수 있는 인원수를 구해 심사받는인원를 충족하면서 시간이 최소인것을 찾는다고 생각하면된다.
return answer;
}
댓글