문제 설명
현대모비스는 우수한 SW 인재 채용을 위해 상시로 채용 설명회를 진행하고 있습니다. 채용 설명회에서는 채용과 관련된 상담을 원하는 참가자에게 멘토와 1:1로 상담할 수 있는 기회를 제공합니다. 채용 설명회에는 멘토 n명이 있으며, 1~k번으로 분류되는 상담 유형이 있습니다. 각 멘토는 k개의 상담 유형 중 하나만 담당할 수 있습니다. 멘토는 자신이 담당하는 유형의 상담만 가능하며, 다른 유형의 상담은 불가능합니다. 멘토는 동시에 참가자 한 명과만 상담 가능하며, 상담 시간은 정확히 참가자가 요청한 시간만큼 걸립니다.
참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.
상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다.
만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다.
모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다.
참가자의 상담 요청 정보가 주어질 때, 참가자가 상담을 요청했을 때부터 상담을 시작하기까지 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정하려 합니다. 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.
상담 유형의 수를 나타내는 정수 k, 멘토의 수를 나타내는 정수 n과 참가자의 상담 요청을 담은 2차원 정수 배열 reqs가 매개변수로 주어집니다. 멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값을 return 하도록 solution 함수를 완성해 주세요.
제한사항
- 1 ≤ k ≤ 5
- k ≤ n ≤ 20
- 3 ≤ reqs의 길이 ≤ 300
- reqs의 원소는 [a, b, c] 형태의 길이가 3인 정수 배열이며, c번 유형의 상담을 원하는 참가자가 a분에 b분 동안의 상담을 요청했음을 의미합니다.
- 1 ≤ a ≤ 1,000
- 1 ≤ b ≤ 100
- 1 ≤ c ≤ k
- reqs는 a를 기준으로 오름차순으로 정렬되어 있습니다.
- reqs 배열에서 a는 중복되지 않습니다. 즉, 참가자가 상담 요청한 시각은 모두 다릅니다.
정답 설명
우리가 구해야 하는 것은 '모든 참가자가 상담을 받을 때 까지 기다려야 하는 시간들의 합의 최솟값' 입니다.
구해야 하는 것이 어떤 것의 최솟값 임을 확인 후 가장 먼저 들었던 생각은 '파라메트릭 서치'가 가능한가 입니다.
그러나 변수, 즉 각 타입에 배정되는 상담원의 수를 전부 고려해야 하기 때문에 파라메트릭 서치의 조건인 '정답 후보가 주어졌을 때, 정답을 검증할 수 있는가?' 를 만족하기 어려워 보였습니다.
제한 사항에서 확인할 수 있는 것 처럼 타입과 상담원의 수, 상담자의 수가 모두 큰 수가 아님을 확인 했고, '각 타입마다 상담원을 한 명씩 늘려가며 상담자가 기다리는 시간을 계산' 하여 최소 시간을 구하는 방법을 선택했습니다.
이제, 우리에게 가장 중요한 것은 "특정 타입에 배정된 상담자가 A 명일 경우 해당 타입의 상담자는 얼마나 오랫동안 기다려야 하는가?" 를 구하는 것입니다.
이는 A명의 상담자를 우선순위 큐에 넣은 뒤, 각 상담에 대해 가장 빨리 상담을 받을 수 있는 상담사를 선택하는 방법으로 구현할 것입니다.
다음으로는 "상담사를 어떤 방식으로 늘려나가야 하는가?" 에 대한 문제가 남아 있습니다.
이 때, '가장 오랜 시간 기다리는 타입'의 상담사를 늘려 나가는 방법을 선택한다면 문제가 해결되지 않습니다. 우리의 목적은 시간의 최솟값을 구하는 것이고, '가장 오랜 시간 걸리는 타입'이 아닌, '상담사를 늘렸을 때, 가장 큰 폭으로 시간이 감소하는 타입'에 상담사를 투입하여야 합니다.
이를 구현하기 위해서는 각 타입 별로 상담사 수에 따른 대기 시간을 모두 구한 후, 남은 상담사가 없을 때 까지 '가장 큰 폭으로 대기 시간이 감소할 수 있는 타입'에 상담사를 추가합니다.
이 역시 우선 순위 큐를 이용하여 쉽게 상담사를 추가할 타입을 확인할 수 있습니다.
이 문제는 우선순위 큐를 이용해 최댓값, 최솟값을 빠르게 얻을 수 있는 방법을 연습하며, 각 상황에 대해 최선의 선택만을 반복해 결과를 얻는 그리디 알고리즘을 사용하는 문제 라고 정리할 수 있을 것 같습니다.
소스 코드
import java.util.*;
class Solution {
public int solution(int types, int mentos, int[][] reqs) {
int[] mentoList = new int[types];
int[] waitingTime = new int[types];
LinkedList<Request>[] requests = new LinkedList[types];
PriorityQueue<Effect> pq = new PriorityQueue<>();
int[][] resultMap = new int[types][mentos+1];
for(int i = 0; i<types; i++){
mentoList[i] = 1;
requests[i] = new LinkedList<>();
}
int remainMento = mentos - types;
for(int[] request : reqs){
Request r = new Request(request[0], request[1]);
requests[request[2] - 1].add(r);
}
for(int i = 0; i < types; i++){
for(int mento = 1; mento <= mentos; mento++){
resultMap[i][mento] = this.getWaitingTime(requests[i], mento);
}
}
if(types == mentos){
int answer = 0;
for(int j = 0; j<types; j++){
answer += resultMap[j][mentoList[j]];
}
return answer;
}
for(int i = 0; i<types; i++){
waitingTime[i] = resultMap[i][1];
pq.add(new Effect(i, resultMap[i][1] - resultMap[i][2]));
}
while(remainMento-- > 0){
Effect maxEffect = pq.poll();
int type = maxEffect.type;
mentoList[type]++;
int mentoNumber = mentoList[type];
pq.add(new Effect(type, resultMap[type][mentoNumber] - resultMap[type][mentoNumber+1]));
}
int answer = 0;
for(int i = 0; i<types; i++){
answer += resultMap[i][mentoList[i]];
}
return answer;
}
private int getWaitingTime(LinkedList<Request> requests, int mentos){
PriorityQueue<Integer> waiting = new PriorityQueue<>();
int time = 0;
for(int i = 0; i<mentos; i++)
waiting.add(0);
for(Request req : requests){
int start = waiting.poll();
int waitingTime = start - req.startTime;
if(waitingTime > 0){
time += waitingTime;
waiting.add(start + req.duringTime);
}
else{
waiting.add(req.startTime + req.duringTime);
}
}
return time;
}
}
class Effect implements Comparable<Effect>{
int type;
int effect;
public Effect(int type, int effect){
this.type = type;
this.effect = effect;
}
public int compareTo(Effect e){
return e.effect - this.effect;
}
}
class Request{
int startTime;
int duringTime;
public Request(int startTime, int duringTime){
this.startTime = startTime;
this.duringTime = duringTime;
}
}
댓글