[프로그래머스] 야근 지수(Lv. 3) C++ 풀이

문제 링크

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

분류

구현, 우선순위, 그리디 알고리즘

시도한 방법

문제에서 원하는 야근 피로도는 남은 작업양의 제곱합으로 구한다. 

제곱은 대상 수가 클수록 더 빠르게 커지므로, 작업 개수 자체가 줄어드는 것 보다 각 작업의 남은 시간을 최대한 균일하고 적게 만드는 편이 제곱합을 줄이는 더 좋은 방법이다.

 

단순하게 남은 시간만큼 루프를 돌며 가장 큰 값에서 1씩 감산하는 방법을 선택했다.

남은 작업량을 대상으로 Priority Queue를 사용하면 항상 가장 많이 남은 작업이 맨 앞으로 오기 때문에, 루프를 돌면서 Priority Queue의 맨 앞 작업이 1씩 감산하게 작성했다.

 

한 Epoch당 남아있는 작업량이 가장 많은 경우를 찾아야 하므로, Greedy 알고리즘에 가장 적합하다. 

결과 코드

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

using namespace std;

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

    for (auto it : works)
        worksList.push(it);

    while (n-- && !worksList.empty())
    {
        int top = worksList.top();
        worksList.pop();

        if (top > 0)
            worksList.push(top - 1);
    }

    while (!worksList.empty())
    {
        long long largest = worksList.top();
        worksList.pop();
        answer += largest * largest;
    }

    return answer;
}