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

1. 문제 풀이

최대 힙을 사용하여 top값을 1 감소시키고 다시 힙에 삽입하는 과정을 n번 반복합니다. 이때 감소한 결과가 0이 되면 삽입하지 않습니다. 최대 힙에 남아있는 값들을 모두 제곱하여 더한 뒤 반환하면 풀이할 수 있습니다.

 

works의 크기를 m이라고 한다면 시간복잡도는 O(n log m)입니다.

 

2. 코드

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

priority_queue<int> pq;

long long solution(int n, vector<int> works) {
    for(auto x : works) pq.push(x);
    
    while(n-- && pq.size()){
        auto cur = pq.top(); pq.pop();
        cur--;
        if(cur) pq.push(cur);
    }
    
    ll ans{};
    while(pq.size()){
        ll cur = pq.top(); pq.pop();
        ans += cur * cur;
    }
    
    return ans;
}