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

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

프로그래머스

 

해결 방법

• 동일한 타입의 상담을 원하는 유저들끼리 모은다. types[i] 에는 타입이 i인 고객들이 들어있다.  (정렬은 이미 되어있다고 하니, 할 필요없다.)
• 모든  타입에 상담원을 한명씩 배치한 tutors 를 만든다. tutors[i] 는 타입이 i인 부스의 상담원 수이다.
• 이제 한명씩 상담원을 배치할건데,  getWait을 이용하여 상담원이 N명일 경우 기다려야하는시간을 구한다. 현재 상담원 수  기준 기다리는 시간이 a분이고 현재 상담원+1 명 기준 기다리는 시간 b를 구한다.
• a-b , 즉, 상담원을 한명 늘림에 따라 이득볼수있는 시간인 effect를 구한다. 
• 가장 effect가 좋은 창구에 상담원을 한명 늘려준다.
• 모든상담원이 배치되면 종료된다. 마지막으로, 모든 상담구에서 유저들이 기다리는 시간을 더한다.

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

using namespace std;

int getWait(vector<pair<int,int>>& reqs, int tutor){
    vector<int> tutors(tutor,0);
    int minute =0;
    for(int i=0; i<reqs.size();i++){
        int min_tutor = -1;
        bool flag = false;
        for(int j = 0; j<tutors.size(); j++){
            if(tutors[j]<=reqs[i].first){ //안기다려도됨.
                tutors[j] = reqs[i].first + reqs[i].second;
                flag = true;
                break;
            }
            
            if(min_tutor == -1 || tutors[j] < tutors[min_tutor]) min_tutor = j;
        }
        
        //비어있는 상담원 없음. 기다려야됨.기다린 시간을 더해주고, 입장
        if(!flag){
            minute += tutors[min_tutor] - reqs[i].first;
            tutors[min_tutor] = tutors[min_tutor] + reqs[i].second;    
        }
    }
    
    return minute;
}

int solution(int k, int n, vector<vector<int>> reqs) {

    vector<int> tutors(k+1,1);
    int remain = n-k;
    
    //동일한 타입끼리 모으기
    vector<vector<pair<int,int>>> types(k+1, vector<pair<int,int>>());
    for(const auto& v : reqs){
        types[v[2]].push_back(make_pair(v[0],v[1]));
    }

    //남은상담원이 없을때까지
    while(remain > 0){
        int max = 0 ; int idx = 0;
        for(int i=1; i<=k ; i++){
            //현재상담원+1 명일때와 상담원일때 기다리는 시간의 차이를 구함.
            int effect = getWait(types[i], tutors[i]) - getWait(types[i], tutors[i]+1);
            if(max < effect){
                max = effect;
                idx  = i;
            }
        }
        //가장 효율좋은 창구에 상담원 증가
        tutors[idx] +=1;
        remain--;
    }
    
    //마지막으로 기다리는 시간 총합 구하기
    int sum =0;
    for(int i=1; i<=k; i++) sum +=  getWait(types[i],tutors[i]);
    
    return sum;
}