프로그래머스[Lv.3] - 상담원 인원

문제 설명

현대모비스는 우수한 SW 인재 채용을 위해 상시로 채용 설명회를 진행하고 있습니다. 채용 설명회에서는 채용과 관련된 상담을 원하는 참가자에게 멘토와 1:1로 상담할 수 있는 기회를 제공합니다. 채용 설명회에는 멘토 n명이 있으며, 1~k번으로 분류되는 상담 유형이 있습니다. 각 멘토는 k개의 상담 유형 중 하나만 담당할 수 있습니다. 멘토는 자신이 담당하는 유형의 상담만 가능하며, 다른 유형의 상담은 불가능합니다. 멘토는 동시에 참가자 한 명과만 상담 가능하며, 상담 시간은 정확히 참가자가 요청한 시간만큼 걸립니다.

참가자가 상담 요청을 하면 아래와 같은 규칙대로 상담을 진행합니다.

• 상담을 원하는 참가자가 상담 요청을 했을 때, 참가자의 상담 유형을 담당하는 멘토 중 상담 중이 아닌 멘토와 상담을 시작합니다.
• 만약 참가자의 상담 유형을 담당하는 멘토가 모두 상담 중이라면, 자신의 차례가 올 때까지 기다립니다. 참가자가 기다린 시간은 참가자가 상담 요청했을 때부터 멘토와 상담을 시작할 때까지의 시간입니다.
• 모든 멘토는 상담이 끝났을 때 자신의 상담 유형의 상담을 받기 위해 기다리고 있는 참가자가 있으면 즉시 상담을 시작합니다. 이때, 먼저 상담 요청한 참가자가 우선됩니다.

참가자의 상담 요청 정보가 주어질 때, 참가자가 상담을 요청했을 때부터 상담을 시작하기까지 기다린 시간의 합이 최소가 되도록 각 상담 유형별로 멘토 인원을 정하려 합니다. 단, 각 유형별로 멘토 인원이 적어도 한 명 이상이어야 합니다.

예를 들어, 5명의 멘토가 있고 1~3번의 3가지 상담 유형이 있을 때 아래와 같은 참가자의 상담 요청이 있습니다.

 

참가자의 상담 요청

참가자 번호	시각	상담 시간	상담 유형
1번 참가자	10분	60분	1번 유형
2번 참가자	15분	100분	3번 유형
3번 참가자	20분	30분	1번 유형
4번 참가자	30분	50분	3번 유형
5번 참가자	50분	40분	1번 유형
6번 참가자	60분	30분	2번 유형
7번 참가자	65분	30분	1번 유형
8번 참가자	70분	100분	2번 유형

이때, 멘토 인원을 아래와 같이 정하면, 참가자가 기다린 시간의 합이 25로 최소가 됩니다.

 

1번 유형

1번 유형을 담당하는 멘토가 2명 있습니다.

• 1번 참가자가 상담 요청했을 때, 멘토#1과 10분~70분 동안 상담을 합니다.
• 3번 참가자가 상담 요청했을 때, 멘토#2와 20분~50분 동안 상담을 합니다.
• 5번 참가자가 상담 요청했을 때, 멘토#2와 50분~90분 동안 상담을 합니다.
• 7번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 1번 참가자의 상담이 끝날 때까지 5분 동안 기다리고 멘토#1과 70분~100분 동안 상담을 합니다.

 

2번 유형

2번 유형을 담당하는 멘토가 1명 있습니다.

• 6번 참가자가 상담 요청했을 때, 멘토와 60분~90분 동안 상담을 합니다.
• 8번 참가자가 상담 요청했을 때, 모든 멘토가 상담 중이므로 6번 참가자의 상담이 끝날 때까지 20분 동안 기다리고 90분~190분 동안 상담을 합니다.

 

3번 유형

3번 유형을 담당하는 멘토가 2명 있습니다.

• 2번 참가자가 상담 요청했을 때, 멘토#1과 15분~115분 동안 상담을 합니다.
• 4번 참가자가 상담 요청했을 때, 멘토#2와 30분~80분 동안 상담을 합니다.

상담 유형의 수를 나타내는 정수 k, 멘토의 수를 나타내는 정수 n과 참가자의 상담 요청을 담은 2차원 정수 배열 reqs가 매개변수로 주어집니다. 멘토 인원을 적절히 배정했을 때 참가자들이 상담을 받기까지 기다린 시간을 모두 합한 값의 최솟값을 return 하도록 solution 함수를 완성해 주세요.

https://school.programmers.co.kr/learn/courses/30/lessons/214288?language=cpp#

프로그래머스

---

 

 

 

 

 

 

제한 사항

• 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는 중복되지 않습니다. 즉, 참가자가 상담 요청한 시각은 모두 다릅니다

---

 

 

 

 

 

 

풀이

처음엔 n, k가 그리 크지 않았기 때문에 dfs로 풀 수 있을 것이라고 생각했다.

n명의 상담원을 k개의 타입에 배치하는 모든 경우의 수를 구해서 배치가 완료되면 대기시간을 구하려 했다.

하지만, 시간초과로 실패했다.

 

성공한 풀이법은 다음과 같다.

문제를 풀기 위해서는 두 가지 부분을 해결해야 한다.

1. 대기시간 구하기
2. 상담원 배치

우선 대기시간을 구하는 법은 priority_queue를 사용하는 것이다.

상담은 요청된 순으로 처리해야 하지만, 상담이 종료되는 순간은 요청된 순서와 다르다. 

즉, 종료되는 시간을 priority_queue로 관리하여 일찍 종료되는 요청을 기준으로 대기시간을 계산하면 된다.

만약, 이전 요청의 종료시간과 현재 요청의 시작시간이 같거나 더 느리다면 대기할 필요가 없다.

priority_queue<int, vector<int>, greater<int>> endTime;

int firstEnd = endTime.top();
endTime.pop();

if(start <= firstEnd)
{
    //대기
    waitTime += (firstEnd-start);
    endTime.push(firstEnd+time);
}
else
{
    endTime.push(start+time);
}

 

 

상담원을 배치하는 문제는 각 타입에 상담원이 1~n명을 배치한 경우의 대기시간을 계산하여 기록해 놓으면 된다.

타입\상담원 인원	1	2	3	4	5
1	175	5	0	0	0
2	20	0	0	0	0
3	85	0	0	0	0

 

각 타입에는 적어도 1명의 상담원이 배치되어야 한다.

그 상태에서 특정 타입에 인원이 배치되었을 경우 가장 이득이 되는 경우를 k개의 타입에 대해 계산하여 구하면 된다.

• 1번 타입에 배치된 경우: 175 → 5
• 2번 타입에 배치된 경우: 20 → 0
• 3번 타입에 배치된 경우: 85 → 0

대기시간이 가장 많이 줄어드는 경우는 1번에 배치된 경우이다. 

기본적으로 1명씩 배치된 상담사를 제외한 나머지 상담사를 계산하면 된다.

vector<int> counselor(k+1, 1);

for(int i = 0; i < n-k; i++)
{
    int maxVal = 0;
    int maxIdx = 0;
    for(int j = 1; j <= k; j++)
    {
        int idx = counselor[j];
        if(maxVal < wait[j][idx] - wait[j][idx+1])
        {
            maxVal = wait[j][idx] - wait[j][idx+1];
            maxIdx = j;
        }
    }
    counselor[maxIdx]++;
}

---

 

 

 

 

 

전체 코드

#include <string>
#include <vector>
#include <algorithm>
#include <queue>
#include <cmath>
#include <iostream>

using namespace std;

int cal(int k, int n,vector<vector<int>>& reqs)
{
    int waitTime = 0;
    priority_queue<int, vector<int>, greater<int>> endTime;
    for(auto req: reqs)
    {
        int start = req[0];
        int time = req[1];
        int type = req[2];
        
        if(type != k) continue;
        
        if(endTime.size() < n){
            endTime.push(start+time);
            continue;
        }
        
        int firstEnd = endTime.top();
        endTime.pop();
        
        if(start <= firstEnd)
        {
            //대기
            waitTime += (firstEnd-start);
            endTime.push(firstEnd+time);
        }
        else
        {
            endTime.push(start+time);
        }
    }
    
    return waitTime;
}


int solution(int k, int n, vector<vector<int>> reqs) {
    int answer = 0;
    
    vector<int> counselor(k+1, 1);
    vector<vector<int>> wait(k+1, vector<int>(n+1, 0));
    //k유형
    for(int i = 1; i <= k; i++)
    {
        //n명씩 배치
        for(int j = 1; j <= n; j++)
        {
            wait[i][j] = cal(i, j, reqs);
        }
    }
    
    for(int i = 0; i < n-k; i++)
    {
        int maxVal = 0;
        int maxIdx = 0;
        for(int j = 1; j <= k; j++)
        {
            int idx = counselor[j];
            if(maxVal < wait[j][idx] - wait[j][idx+1])
            {
                maxVal = wait[j][idx] - wait[j][idx+1];
                maxIdx = j;
            }
        }
        counselor[maxIdx]++;
    }
    
    for(int i = 1; i <= k; i++)
    {
        answer += wait[i][counselor[i]];
    }

    
    return answer;
}

---