링크 : https://school.programmers.co.kr/learn/courses/30/lessons/214288
문제 설명
H회사 채용 설명회에서 k개의 부서에 대해 n명의 멘토가 상담을 할 예정입니다.
상담 신청서 뭉치 reqs에는 [상담 시작 시간, 상담 소요 시간, 상담 부서] 3가지가 기입된 신청서들이 있습니다.
다음과 같은 조건하에 각 신청자가 최대한 기다리지 않도록 부서당 멘토 비율을 조정해야 합니다.
- 상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다.
- 만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다.
- 모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다.
- 각 부서에는 최소한 1명의 멘토는 있어야합니다.
멘토를 적절히 조정했을 때 상담을 받기까지 기다린 시간에 최솟값을 리턴하시오.
아이디어
1. 여러 조건이 합쳐진 것처럼 보일 수 있지만 결국 상담은 부서별로 이루어지기 때문에 각 부서간에 멘토 수에 따른 탐욕법으로 해당 부서에 최소 대기시간을 확인합니다.
2. k개의 부서에 멘토가 i1, i2, ...ik명 있을 때 멘토가 1명 늘어났을 때 가장 대기 시간이 줄어드는 곳에 1명을 추가해주고 이 과정을 멘토가 총 n명이 될 때까지 해줍니다.
3. 비율이 모두 조정됐다면 각 부서별 대기시간을 합해줍니다.
코드
#include <string>
#include <vector>
using namespace std;
vector<vector<pair<int, int>>> waitingQues(5);
vector<int> mentos(5);
int answer = 0;
int CheckWaitingTime(int category)
{
int totalWaitingTime = 0;
int mentoNum = mentos[category];
vector<pair<int, int>> consultings(mentoNum);
for(auto counselor : waitingQues[category])
{
if(mentoNum > 0) consultings[--mentoNum] = counselor;
else
{
int firstFinshMento;
int finishTime = 2e9;
bool noWaitingTime = false;
for(int i = 0; i < consultings.size(); i++)
{
int consultingFinishTime = consultings[i].first + consultings[i].second;
if(consultingFinishTime < counselor.first)
{
consultings[i] = counselor;
noWaitingTime = true;
break;
}
else if(finishTime > consultingFinishTime)
{
finishTime = consultingFinishTime;
firstFinshMento = i;
}
}
if(noWaitingTime) continue;
totalWaitingTime += finishTime - counselor.first;
consultings[firstFinshMento].first = consultings[firstFinshMento].first + consultings[firstFinshMento].second;
consultings[firstFinshMento].second = counselor.second;
}
}
return totalWaitingTime;
}
int solution(int k, int n, vector<vector<int>> reqs) {
//1. init
for(auto req : reqs)
{
waitingQues[req[2]-1].push_back({req[0], req[1]});
}
for(int i = 0; i < k; i++)
{
mentos[i] = 1;
}
n -= k;
//2. check bestImproved solution category when mento+1
for(int i = 0; i < n; i++)
{
int bestImprovedQue = -1;
int bestImprovedTime = -1;
for(int j = 0; j < k; j++)
{
int beforeWaitingTIme = CheckWaitingTime(j);
mentos[j]++;
int afterWaitingTime = CheckWaitingTime(j);
mentos[j]--;
if(bestImprovedTime < abs(beforeWaitingTIme - afterWaitingTime))
{
bestImprovedQue = j;
bestImprovedTime = abs(beforeWaitingTIme - afterWaitingTime);
}
}
mentos[bestImprovedQue]++;
}
//3. check all line Waiting time
for(int i = 0; i < k; i++)
{
answer += CheckWaitingTime(i);
}
return answer;
}
피드백
1. 최초에는 가장 대기시간이 긴 시간대에 멘토를 추가해주는 방법으로 했었는데, 멘토가 추가되도 반드시 가장 대기시간이 개선되는지 알 수 없어 멘토가 추가되었을 때의 대기시간과 그렇지 않은 시간에 차이로 변경
2. CheckWaitingTime()에서 다음 상담자가 대기시간이 없음에도 처리를 안해서 음수가 되는 상황
3. 처음 푼 코드가 이상하게 안되서 그 코드를 보고 다시 깔끔히 작성하니 됐는데, 기존 코드가 왜 안된지 확신이 안드는 문제..
'알고리즘' 카테고리의 다른 글
프로그래머스 - 표 병합(150366) (0) | 2023.08.29 |
---|---|
프로그래머스 - 합승 택시 요금(72413) (0) | 2023.08.29 |
프로그래머스 - 보석 쇼핑(67258) (0) | 2023.07.07 |
프로그래머스 - 수식 최대화(67257) (0) | 2023.07.06 |
프로그래머스 - k진수에서 소수 개수 구하기(92335) (0) | 2023.06.28 |