[C++] 상담원 인원

[문제]

코딩테스트 연습 - 상담원 인원 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

[문제 풀이]

백트래킹 + 우선순위큐를 이용해서 풀 수 있는 문제였다.

 

우선 백트래킹을 이용해서 내가 정해줄 수 있는 멘토의 수를 모두 정한다.

k가 3이고 n이 5라면 (1,1,3), (1,2,2), (1,3,1), (2,1,2), (2,2,1), (3,1,1)의 6가지가 나오면 된다.

여기서 중요한것은 완전 탐색이 아닌 백트래킹이라는 점이다.

문제에서 보면 모든 멘토는 1부터 시작이고 멘토들을 모두 합친 값은 n이 나와야 한다.

즉, 벡터의 total이 n을 넘는순간 return으로 가지치기를 하는 백트래킹 유형이다.

 

int total;

void backTrack(int k, int n){
    
    if(vec.size() == k){
    	//만일 total값이 n이 아니라면 종료
        if(total != n){
            return;
        }
        //해당 멘토들로 최소값이 몇이 나올지 파악하는 함수.
        timeTable();        
        return;
    }
    
    //시작은 1이고 최댓값은 n - k + 1
    for(int i = 1;i<=n - k + 1;i++){
    	//만일 total값이 n을 넘게 된다면 바로 가지치기.
        if((total + i) > n){
            return;
        }
        vec.push_back(i);
        total += i;
        backTrack(k,n);
        total -= i;
        vec.pop_back();
    }
    
    return;
}

 

위와 같은 코드를 사용해서 백트래킹을 할 수 있고 이제 해당 멘토들의 수를 알 수가 있으니 이 수를 이용해서 나올 수 있는 최소값이 몇인지 파악하는 함수를 만들자.

 

우선순위 큐를 사용해서 아래와 같은 변수를 선언해주자.

priority_queue<int, vector<int>, greater<int> > pq[10];

 

우선순위 큐인 pq에서 뒤에 있는 인덱스는 reqs[i][2] 즉, 몇번째 멘토한테 넣을지 파악하는 인덱스이고 종료시간이 빠른 순서부터 작업이 끝날테니 greater<int> 를 통하여 정렬을 해주었다.

 

이제 reqs 변수를 처음부터 끝까지 차례대로 방문하면서

1. 지금 넣어져 있는 우선순위 큐의 종료시간 보다 지금 타입의 시작 시간이 빠르다면 

2. 해당 타입의 멘토가 비어있다면

3. 만일 해당 타입의 멘토가 모두 차있다면

의 3가지 조건을 정해서 반복문을 돌려주자.

 

주의사항이 있다면 pq에 넣어야 하는건 종료시간이고 종료시간은 reqs[i][0] + reqs[i][1]이 아닐 수 있다는 것이다.

[회고]

백트래킹 부분에서 1차로 헷갈리고 pq 부분에서 2차로 헷갈렸던 문제.

하나 하나가 어렵지는 않지만 함수화를 통해서 백트래킹을 먼저 하고 두번째로 해당 멘토들의 최소값이 몇이 나오는지를 함수화로 또 만들어야 하는데 함수에서 함수를 통할수록 코드에서 틀린 부분이 나올 때 잡아내기가 쉽지 않다는 것이 문제이다.

 

백트래킹 쪽은 가지치기를 해야하는데 중복조합이란 것에 코드 의식이 쏟아지다 보니 가지치기를 안하고 있어서 처음에 원하는 값이 안나왔고 pq는 조건 부분에서 계속 하나씩 놓쳐가지고 몇번의 오류를 겪었다.

어려울 만한 문제이긴 하지만 못 풀 만한 문제는 아니다. 1시간 내로 해당 문제를 풀 실력을 갖추도록 하자.

[코드]

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
using namespace std;

vector<int> vec;
int total;
int min_answer = 9999999;
vector<vector<int> > reqs;

void timeTable(){
    int answer = 0;    
    
    //mentor가 몇명인지 파악하는 변수.
    vector<int> mentor = vec;
    
    //i번 멘토와 상담중인 참가자가 언제 끝날지를 저장할 변수.
    //pq는 작업 종료시간을 기록할 우선순위 큐 ( 상담시간 + 현재시간)
    priority_queue<int, vector<int>, greater<int> > pq[10];
    
    for(int i = 0;i<reqs.size();i++){
        //만일 넣을 수 있다면.
        int type = reqs[i][2];
        if(pq[type].size() > 0 && pq[type].top() < reqs[i][0]){
            pq[type].pop();
            mentor[type - 1]++;
        }
        
        if(mentor[type - 1] >= 1){
            //종료시간 넣기.
            pq[type].push(reqs[i][0] + reqs[i][1]);
            mentor[type - 1]--;
        }
        else if(mentor[type - 1] <= 0){
            int startTime = pq[type].top();
            answer += startTime - reqs[i][0];
            pq[type].pop();
            //종료시간 넣기.
            pq[type].push(startTime + reqs[i][1]);
        }
    }

    min_answer = min(min_answer,answer);
    return;
}


void dfs(int k, int n){
    
    if(vec.size() == k){
        if(total != n){
            return;
        }
        timeTable();        
        return;
    }

    for(int i = 1;i<=n - k + 1;i++){
        if((total + i) > n){
            return;
        }
        vec.push_back(i);
        total += i;
        dfs(k,n);
        total -= i;
        vec.pop_back();
    }
    
    return;
}

int solution(int k, int n, vector<vector<int>> req) {
    int answer = 0;
    reqs = req;
    
    dfs(k,n);
    answer = min_answer;
    
    return answer;
}