프로그래머스 Level 3 야근지수

야근지수 (프로그래머스 Level 3)

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

처음에는 수학쪽 문제인 줄 알고
‘남은 양’의 ‘합’을 가능한 동일하게 나누는 방식을 취하였으나
알고 보니 ‘works’ 내부의 요소를 ‘줄이는 것’ 이였다
(도움이 된 예제는 10, {10,10,1} -> 51)
({5,5,1} 이 되어야 하기에 ‘1’인 작업은 건드릴 수 없음)

그렇기에
‘남은 작업’ 중 ‘가장 높은 수치’의 녀석을 ‘가능한 깎아내는 방식’을
반복적으로 취해야 한다고 생각하였다

1. 가장 높은 수치를 ‘매번’ 가져올 수 있도록 ‘우선순위 큐’를 사용
   
2. ‘가능한 깎아내기 위해’ pq.top() -> pq.pop() -> pq.top() 로
   2번째 큰 요소와의 차이를 비교
   이후 그걸 다시 깎을 수 있는 최대치인 n과 비교하는 방식
   (다만 이 부분은 개선 여지가 있을 수 있다 생각)
   

그 외에
처음에 모든 요소의 합이 ‘n’보다 작은 경우는
return 0을 함으로서 예외처리를 해주었다

Code

#include <string>
#include <vector>
#include<numeric>
#include<math.h>
#include<queue>

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;

    long long sum = accumulate(works.begin(), works.end(), 0) - n;

    if (sum <= 0)
        return 0;

    const int wSize = works.size();

    priority_queue<int, vector<int>, less<int>> pq;
    
    for (auto w : works)
    {
        pq.push(w);
    }
    
    while (n > 0)
    {
        int t = pq.top();
        pq.pop();
        int dist = t - pq.top() + 1;

        if (dist > n)
        {
            dist = n;
        }
        
        t -= dist;
        n -= dist;

        pq.push(t);
    }


    while (pq.empty() == false)
    {
        answer += pow(pq.top(), 2);
        pq.pop();
    }

    return answer;
}