[Algorithm] Programmers :: 상담원 인원

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

프로그래머스

struct Worker
{
    int endTime = -1000000000;
};
 
struct cmp
{
    bool operator() (const Worker& a, const Worker& b)
    {
        return a.endTime > b.endTime;
    }
};
 
int maxDepth = 0; // 창구갯수
int maxNum = 0; // 한창구에 배정받을 수 있는 최대인원.
int answer = 0x3f3f3f3f;
 
vector<vector<int>> reques[6];
vector<int> combi;
 
void Calc()
{
    int sum = 0;
 
    for (int i = 1; i <= maxDepth; ++i) // 각 창구.
    {
        int workers = combi[i];
 
        Worker arr[20];
        priority_queue<Worker, vector<Worker>, cmp> pq(arr, arr + workers);
 
        vector<vector<int>>& reqs = reques[i];
 
        for (int j = 0; j < reqs.size(); ++j)
        {
            Worker worker = pq.top();
            pq.pop();
 
            int startTime = reqs[j][0];
            int workTime = reqs[j][1];
 
            if (worker.endTime <= startTime) // 대기시간이 없는경우
            {
                worker.endTime = startTime + workTime;
            }
            else // 대기시간 있는경우
            {
                sum += worker.endTime - startTime;
                worker.endTime = worker.endTime + workTime;
            }
 
            pq.push(worker);
        }
    }
 
    answer = min(answer, sum);
}
 
void DFS(int depth, int availablePeople)
{
    if (depth == maxDepth)
    {
        combi[depth] = availablePeople;
        Calc();
        return;
    }
 
    for (int i = 1; i <= maxNum; ++i)
    {
        if (availablePeople - i >= maxDepth - depth) // 마지막창구에 최소 1명 배치되야하니까
        {
            combi[depth] = i;
            DFS(depth + 1, availablePeople - i);
        }        
    }
}
 
int solution(int k, int n, vector<vector<int>> reqs)
{
    maxDepth = k;
    maxNum = n - k + 1;
    vector<int> temp(n + 1);
    combi = temp;
 
    for (int i = 0; i < reqs.size(); ++i)
    {
        reques[reqs[i][2]].push_back(reqs[i]);
    }
 
    if (k == 1)
    {
        combi[1] = n;
        Calc();
        return answer;
    }
 
    for (int i = 1; i <= maxNum; ++i)
    {
        combi[1] = i;
        DFS(2,n-i);
    }
 
    return answer;
}

아이디어 자체는 생각보다 빨리 알았는데, 별거아닌것같은 구현에서 시간을 좀 쓴 문제..

 

일단 완전탐색느낌으로 생각해냈고, n,k값이 작아서 가능하긴 하다.

각 창구마다의 인원배정의 경우의수를 모두 뽑아낸다.

예를들어 문제예시1번처럼 n = 5, k =3이라면 경우의 수는 다음과 같다.

 

1 1 3

1 2 2

1 3 1

2 1 2

2 2 1

3 1 1

 

이렇게 모든 경우의 수를 뽑고, 이 인원대로 주어진 요청을 전부 처리하는 것이다.

요청을 처리할때는 우선순위큐를 이용했다. 우선순위큐에는 배정받은 인원만큼이 항상 삽입되어있는데, 자기가 마지막으로 처리한 작업시간을 가지고 있는다. 

꺼내는 기준은 마지막작업시간이 가장 작은, 즉 가장 빨리 끝나는 노드를 먼저 꺼낸다.

 

그다음 작업리스트를 순회한다. 요청한 시간대보다 마지막작업시간이 더 작다면, 즉 요청을 바로 처리할 수 있다면 해당 요청의 마지막마무리시간을 업데이트하고 다시 우선순위큐에 넣는다.

만약 요청한 시간대보다 마지막작업시간이 더 크다면, 즉 아직 현재 작업을 처리중이라면 그 시간차이만큼 대기시간에 합산해주고 마지막마무리시간을 업데이트 해주고 우선순위 큐에 집어넣어준다.

 

각 창구마다 요청을 전부처리했다면 최종누적값을 answer에 업데이트 시켜주면 된다.

 

구현할때는 안헷갈릴려고 구조체도 하고 뭐하고 해서 좀 지저분해보이긴 하는데, 다 짜고나니 이것저것 작은 최적화들의 여지가 있는 것 같긴하다. 구조체 멤버변수도 하나밖에없어서 그냥 int로 해도 되긴 한다.

 

의외로 저 각 경우의수 뽑는거에서 헷갈려서 시간 좀 잡아먹었다... 심지어 k값이 1이면 정상작동 안해서 따로 예외처리한것도 볼 수 있다 ㅎㅎ;