상담원 인원 [Lv. 3] (C++)

프로그래머스

k개의 상담 유형과 n명의 멘토가 있고 상담받는 사람들의 도착 시각, 상담 시간, 상담 유형을 받을 때

멘토들의 상담 유형을 선택하여 상담받는 사람들의 최소 대기시간을 구하는 문제입니다.

 

예시) k가 3이고 n이 5일 때 멘토

1번 유형 3명

2번 유형 1명

3번 유형 1명

 

1번 유형 1명

2번 유형 2명

3번 유형 2명

...

...

...

 

여러 케이스로 계산하여 최소 대기 시간을 찾아야 합니다.

 

풀이 방법

우선 멘토 유형의 모든 경우의 수를 찾아야 합니다.

모든 유형을 찾는 것은 백트레킹으로 찾고 따로 보관합니다.

vector<vector<int>> orders;
void backtracking(vector<int> mentos, int idx, int coin)
{
    if (coin == 0){
        orders.push_back(mentos);
        return;        
    }
    
    for (int i = idx; i < mentos.size(); i++)
    {
        mentos[i]++;
        backtracking(mentos, i, coin-1);
        mentos[i]--;
    }
}

 

int answer = Counseling(orders[0], reqs);
for (int i = 1; i < orders.size(); i++)
    answer = min(answer, Counseling(orders[i], reqs));

return answer;

이후 모든 경우의 수로 상담을 진행하고 최소 대기시간을 출력합니다

 

int Counseling(vector<int>& order, vector<vector<int>>& reqs)
{
    priority_queue<int, vector<int>, greater<int>> q[order.size()];
    
    for (int i = 0; i < order.size(); i++)
    {
        while(order[i]-- > 0)
            q[i].push(0);          
        
    }
    
    int ret = 0;
    for (vector<int>& req : reqs)
    {
        int start = req[0];
        int time = req[1];
        int type = req[2] -1;
        
        int mento = q[type].top(); q[type].pop();
                
        if (mento > start)
        {
            ret += mento - start;
            q[type].push(mento + time);
        }
        else if (mento <= start)
        {
            q[type].push(start + time);
        }
    }
    
    
    
    return ret;
}

우선순위 큐를 이용해 멘토를 관리해줍니다.

멘토 수에 맞게 우선순위 큐에 0을 넣어주고

 

내담자가 도착하는 시간에 우선순위 큐에서 하나 빼서 비교합니다.

내담자가 도착하는 시간보다 멘토의 작업이 종료되는 시간이 같거나 더 빠르다면

내담자는 대기 없이 상담이 가능하며 그렇지 않다면 시간 차이만큼 대기를 하게됩니다.

 

이후 상담이 종료되는 시점을 q에 넣어주며 반복합니다.