[프로그래머스/C++] 야근 지수

프로그래머스

 

• 야근지수가 최소가 되려면 작업량을 줄이면서 해당 작업량들간의 차이가 최소가 되어야함
• 작업량을 내림차순으로 정렬한 뒤에 높은 값을 -1씩 해주는걸 반복
• > 우선순위 큐에 작업량을 삽입하고 top을 꺼내서 -1 해주고 다시 삽입을 반복

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

using namespace std;

// works의 시간을 줄이면서 works의 작업량들의 값이 비슷해야함
// 예를 들어 [4,3,3]에서 n = 4일 때 [0,3,3]이 되면 작업 하나는 마쳤지만 야근 지수는 제곱을 해서 0 + 9 + 9 = 18이 됨
// 하지만 [2,2,2]가 되면 4 + 4 + 4 = 12로 최소가 됨
// 우선순위 큐로 제일 많이 남은 작업량을 꺼내서 -1 해주고 다시 담는 걸 n번 반복

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> pq;
    
    for(int i = 0; i < works.size(); i++)
        pq.push(works[i]);
    
    for(int i = 0; i < n; i++) {
        if(pq.empty()) break;
        
        int num = pq.top() - 1;
        pq.pop();
        
        if(num == 0) continue;
        else pq.push(num);
    }
    
    if(pq.empty())
        return 0;
    
    for(int i = 0; !pq.empty(); i++) {
        int num = pq.top();
        answer += num * num ;
        pq.pop();
    }
    
    return answer;
}