프로그래머스 - 야근 지수

프로그래머스 - 야근 지수

야근 피로도가 최소가 되기 위해선 n을 뺏을 때, 배열 내의 원소들끼리 최대한 같은 값을 가지도록해서 차이가 최소가 되어야 한다.

즉, 가장 큰 원소랑 두 번째로 큰 원소의 차이 더하기 1만큼을 가장 큰 원소에서 빼는걸 n이 0이 아닐 때까지 반복하면 된다.

max_element를 이용해서 가장 큰 원소에서 1씩만 반복적으로 빼주는 로직으로는 효율성을 통과하지 못한다.
따라서 가장 큰 원소와 두번 째로 큰 원소를 찾는 것을 priority_queue를 이용했다.

코드는 아래와 같다.

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

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    int s = 0;
    priority_queue<int> pq;
    for(auto it : works) {
        pq.push(it);
        s += it;
    }
    if(n >= s)
        return 0;
    
    while(n) {
        int first_element = pq.top(); pq.pop();
        int diff = first_element - pq.top() + 1;
        if(diff <= n) {
            first_element -= diff;    
            n -= diff;
        } else {
            first_element -= n;
            n = 0;
        }
        pq.push(first_element);
    }
    
    while(!pq.empty()) {
        answer += powl(pq.top(), 2);
        pq.pop();
    }
    
    return answer;
}