프로그래머스 상담원 인원 c++ // 우선순위큐, 중복조합(백트래킹)

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

프로그래머스

 

1. 의사코드

i) 상담사 분배  경의의수 구현

상담유형=5일때, 상담사=20명을 분배해야한다.

이때, 최소 상담사는 1명씩 있어야한다. -> 15명을 5개칸에 분배해야한다

[ 1 1 1 1 1] 

[ 0 0 0 0 0] 서로다른5자리에서 중복을포함해 15개를 고르면된다.

 ex) 첫째자리만 15번고르면 상담사가 [16 1 1 1 1]이 된다.

중복조합의 구현은 st를두고, vis체크를 없애면 된다.

모든 상담사배치에 대해서

모든 요청에대해서 구현을 하면된다.

 

ii) 구현

짧은상담사부터 상담 -> pq를 이용하도록 한다.

0. pq의 값을 정의 : (가장빠른)상담끝나는시간

1. 일단 pq배열을 두고, 유형별 상담가능한 상담사를 배치한다. (0으로 push)

상담사 배치가 311 인경우, 상담사 숫자만큼 push

2. 경우의수가 3가지로나뉜다.

- pq.top == 요청시간인경우 : 대기시간x, 끝나는 즉시 이어서 상담을 한다.

ex) 10에 [10,30]이 들어옴 -> 즉시이어서 상담 == 값을 10(상담사끝나는시간)+30(소요시간) 으로 교체하면된다.

 

- pq.top > 요청시간인경우 : 대기시간o, 끝나는 즉시 이어서 상담을 한다.

ex) 20에 [10,30]이 들어옴 -> 10초(20-10)만큼대기하고 값을 20 (상담사끝나는시간) +30 (소요시간)  으로 교체하면된다.

 

- pq.top < 요청시간인경우 : 대기시간x, 끝나는 즉시 이어서 상담을 한다.

ex) 20에 [30,40]이 들어옴 -> 30초에 40초짜리 상담을 새로 시작하면된다. // 30+40을 push

 

2. 시간복잡도

5H15 == 20C15 ==20 C 5 ==  15504

* 900개 요청

* log(900) : pq 삽입, 삭제

==약 1300만

 

3. 전체코드

#include <bits/stdc++.h>

using namespace std;

vector<vector<int>> reqs;
int ret=987654321;

void go2(vector<int>& v){ // v: 상담사숫자 [3 1 1]
    int wait_time=0;
    //상담사별 대기큐
    //priority_queue<pair<int,int>, vector<pair<int,int>> ,greater<>> q[v.size()]; 
    priority_queue<int, vector<int> ,greater<>> q[v.size()]; 
    //q[0] : 0번 상담사의 대기자 목록, 값 : 상담이끝나는시간
    //상담사 숫자만큼 0으로 채워넣기
    int idx=0;
    for(auto a : v){
        for(int i=0;i<a;++i){
            q[idx].push(0);
        }
        idx++;
    }

    
    for(auto req : reqs){
        //가장짧은상담사가 끝나는 시간 == 요청시작시간 -> 대기시간없이 바로가능
        int idx = req[2]-1; //유형
        
        //if(q[idx].size()==0) continue;
        //가장짧은상담사가 끝나는 시간 == 요청시작시간 -> 대기시간 발생안함, 즉시 이어서상담
        int temp=q[idx].top();
        if(temp ==req[0]){ 
            q[idx].pop();
            q[idx].push(temp+req[1]); //시간갱신 = 
        }
        //가장짧은상담사가 끝나는 시간 > 요청시작시간 -> 대기시간 발생, 즉시 이어서상담
        else if(temp > req[0]){ 
            //cout<<temp<<" "<<req[0]<<" \n";
            //
            wait_time+=abs(temp-req[0]);
            q[idx].pop();
            q[idx].push(temp+req[1]); //시간갱신 = 
        }
        //가장짧은상담사가 끝나는 시간 < 요청시작시간 -> 대기시간 발생안함, 즉시시간갱신
        else if(temp < req[0]){ 
            q[idx].pop();
            q[idx].push(req[0]+req[1]); //시간갱신 = 
        }
    }

    //cout<<wait_time<<"\n";
    ret=min(ret,wait_time);
}

//남은갯수, 뽑은갯수, 중복조합
void go(int remain, int k, vector<int>& v){
    if(remain==0){
        // for(auto i : v){
        //     cout<<i<<" ";
        // }cout<<"\n";
        //orders.push_back(v);
        
        go2(v);
        
        return;
    }
    //[3 1 1] ->(백트랙) [2 2 1] -> [2 1 2]-> ...
    for(int i=k;i<v.size();++i){
        v[i]++;
        go(remain-1,i,v);
        v[i]--;
    }
}

int solution(int k, int n, vector<vector<int>> _reqs) {
    reqs=_reqs;
    
    vector<int> v(k,1); //최소1명씩은 배정되어야하므로 [1, 1, 1]로 초기화
    go(n-k,0,v); //남은 (n-k)명을 분배함
    return ret;
}