[Programmers, C++]#Level3_야근 지수

#1. 문제

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

 

---

 

#2. 풀이

 

1. 우선순위 큐

[자료구조]#7_우선순위 큐

우선순위 큐는 각 항목에 우선순위를 부여하고, 우선순위가 가장 높은 항목부터 차례대로 제거되는 자료구조입니다. 일반적으로, 우선순위 큐는 힙 자료구조로 구현되며, 우선순위 기준에 따라서 최소 힙 혹은 최대 힙을 구성합니다. 따라서, 우선순위 큐는 삽입/삭제/탐색 작업 시 O(log n)의 시간 복잡도를 갖습니다.

 

2. 최대 힙 구성, 남은 시간과 pq.top()의 비교

1. 먼저, 각 작업에 걸리는 소요 시간들을 모두 priority_queue 컨테이너에 삽입합니다.
2. 다음으로, priority_queue 컨테이너를 순회합니다. 이때, 현재 남은 시간이 존재할 경우와 그렇지 않을 경우로 나누어집니다.
3. 현재 남은 시간이 0보다 클 때, pirority_queue의 top()과 다음으로 가장 큰 항목보다 작아질 때까지, top() 값을 -1 해주고, 동시에 현재 남은 시간을 -1 해줍니다. 마지막으로, 이 작업을 통해 현재 작업의 소요 시간이 남아 있을 경우, 다시 prioriy_queue 컨테이너에 삽입해 줍니다.
4. 현재 남은 시간이 남아 있지 않을 때, prioriy_queue의 top() 원소에 대하여 제곱 연산을 수행하고, 이를 최종 결과 값에 더해줍니다.

 

---

 

#3. 코드

/*
    @링크: https://school.programmers.co.kr/learn/courses/30/lessons/12927
    @문제: N시간 동안 각 일에 대한 작업량에 대하여 야근 피로도를 최소화한 값 찾기
    @설명
        1. 야근 피로도 = N시간 이후, 남은 작업량의 ^2를 모두 더한 값
        2. 우선순위 큐, 최대 힙 구성
        3. n > 0일 때, 지속적으로 pq의 최 우선순위 값을 -1, n 값을 -1 해준다.
        4. n == 0이 되면, pq에서 차례대로 값을 뽑아서 제곱해주고, 그 합을 구한다.
*/

#include <string>
#include <vector>
#include <queue>
#include <cmath>

typedef long long ll;

using namespace std;

long long solution(int n, vector<int> works) {
    ll ans = 0;
    priority_queue<int, vector<int>> pq;

    for(int i=0; i<(int)works.size(); ++i)
    {
        pq.push(works[i]);
    }

    // 우선순위 큐 순회
    while(!pq.empty())
    {
        int tmp = pq.top();
        pq.pop();

        if(n > 0)
        {
            while(tmp >= pq.top() && n > 0)
            {
                tmp--;
                n--;
            }
            if(tmp > 0)
                pq.push(tmp);
        }
        else
        {
            ans += (ll)pow(tmp, 2);
        }
    }

    return ans;

}

 

---