[C++] 상담원 인원 (프로그래머스 LEVEL 3)

https://school.programmers.co.kr/learn/courses/30/lessons/214288

프로그래머스

---

문제풀이

완전 탐색으로 풀수 있을까? 생각해보았다.

상담 유형 k가 5이고, 멘토 수 n이 20일 때, 5명은 반드시 각 지정을 해야하므로 나머지 15명을 3곳에 각각 지정하면 된다. 이 경우의 수는 15C3이고, 각 경우마다 reqs 배열을 반복돌아야 하므로 시간초과 발생 우려는 없다. 그래서 완전 탐색으로 풀어도 된다고 생각했다.

 

1. 상담원을 각 상담유형에 배치하는 모든 경우의 수를 구한다.

2. 각 경우마다 상담 대기 최소 시간을 구한다.

 

1. dfs를 돌며 멘토를 상담 유형에 배정한다.

for(int i=idx; i<v.size(); i++) {
        v[i]++;
        dfs(cnt+1, v, i);
        v[i]--;
    }

이때, 인자로 i를 넣어주어야 시간 복잡도를 줄일 수 있다. 이렇게 안하면 중복해서 찾기 때문이다. 난 이걸 실수로 idx로 넣었다가 1시간동안 삽질했다.....

 

2. 각 상담 유형별로 우선순위 큐를 만든다. 만들고 나서 배정된 상담원 만큼 큐에 0을 넣어 초기화 해준다. 이 때 우선순위 큐는 민힙이어야 한다.

reqs 배열을 반복문 돌며 제일 앞의 값을 꺼내온다. 이 값은 처음에 0이다. 각 상담원의 상담 종료 시간이다.

만약 들어온 값의 상담 시작 시간보다 작거나 같다면, 상담시작시간+상담시간 => 즉 상담 종료 시간을 큐에 넣어준다.

만약 들어온 값의 상담 시작시간보다 크다면, 해당 멘티는 기다려야 하므로 wait 값을 계산해 준뒤 상담 종료 시간을 큐에 넣어준다.

 

이렇게 나온 wait 값의 최소값을 비교하면 정답을 구할 수 있다.

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

using namespace std;

int answer = 999999999;
int n, k;
vector<vector<int>> arr;

void dfs(int cnt, vector<int> v, int idx) {
    if(cnt >= n) {
        priority_queue<int> pq[v.size()];
        for(int i=1; i<v.size(); i++) {
            for(int j=0; j<v[i]; j++) {
                pq[i].push(0);
            }
        }
        
        int wait = 0;
        for(int i=0; i<arr.size(); i++) {
            // 큐에서 상담 종료 시간이 가장 작은 값 꺼내옴
            int t = -pq[arr[i][2]].top();
            pq[arr[i][2]].pop();
            
            if(t <= arr[i][0]) {
                t = arr[i][0] + arr[i][1];
            }
            else {
                wait += t-arr[i][0];
                t = t + arr[i][1];
            }
            pq[arr[i][2]].push(-t);
        }
        answer = min(answer, wait);
        return;
    }
    
    for(int i=idx; i<v.size(); i++) {
        v[i]++;
        dfs(cnt+1, v, i);
        v[i]--;
    }
}

int solution(int a, int b, vector<vector<int>> c) {    
    k = a;
    n = b;
    arr = c;
    
    vector<int> mentor(k+1, 1);

    dfs(k, mentor, 1);
    return answer;
}