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

1. 개요

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

프로그래머스

1-1. 설명

회사원 Demi는 야근을 진행할 때 피로도가 야근 시작지점의 남은 일 작업량의 제곱으로 피로도가 쌓인다. N시간동안 야근 피로도를 최소화할 수 있도록 일한다. Demi가 1시간동안 작업량 1만큼 처리가능할 때, 퇴근까지 남은 N 시간과 각 일에 대한 작업량 works에 대해 야근 피로도를 최소화한 값을 리턴하는 함수를 작성한다. 

1-2. 제한 사항

 - works는 길이가 1이상, 20,000 이하 배열

 - works의 원소는 50,000 이하 자연수

 - n은 1,000,000 이하 자연수

---

2.구현

2-1. 풀이

남은 N 시간만큼 큰 숫자를 빼주고 남은 작업량에 제곱을 해주면 된다고 단순하게 생각하여 반복문을 통해 풀었더니, 효율성에서 시간초과가 떴다. 시간 복잡도가 O(N)이라서 그런 것 같다. 힙을 사용하면 O(logN)까지 줄일 수 있으므로, 최대힙을 통해 구현하는 것으로 변경하고 실행했더니 시간초과가 뜨지 않았다.

2-2. 코드

#include <queue>
#include <vector>
#include <algorithm>

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> queue(works.begin(), works.end());
    for (int num = n; num > 0 ; num--) {
        if (!queue.empty()) {
            int maxNumber = queue.top();
            queue.pop();
            queue.push(maxNumber - 1);
            }
    }
    
    while (!queue.empty()) {
        int currentNumber =  queue.top();
        if (currentNumber <= 0) break;
        queue.pop();
        answer += (currentNumber * currentNumber);
    }
    return answer;
}