프로그래머스 문제 - 야근 지수

프로그래머스 야근 지수 문제 풀이를 진행하였습니다.

문제 해석

문제를 읽으면 아래와 같은 해석이 가능합니다.

각 일의 대한 작업량이 주어지며 일할 수 있는 시간 n을 입력받습니다.
일할 수 있는 시간을 사용하여 작업량을 줄여나가며 작업량이 남았을 시 야근을 통해 작업을 할 수 있습니다.
야근을 하면 피로도가 쌓이는데 피로도는 작업량의 제곱만큼 쌓이게 됩니다.
야근에 대한 피로도의 최솟값을 구해야합니다.

문제 풀이

야근의 대한 피로도는 작업량의 제곱이므로 최솟값을 만들기 위해서는 남은 작업량들의 수가 낮아야합니다.
그러기 위해서는 제일 많은 작업량을 찾아 감소시켜야 합니다.
제일 많은 작업량을 빠르고 쉽게 찾기 위하여 우선순위 큐를 이용하여 찾아주었습니다.

전체 코드

이번 문제는 배열의 최댓값을 빠르게 찾아내기만 하면 풀 수 있는 문제였습니다.

#include <bits/stdc++.h>
#include <string>
#include <vector>

using namespace std;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> pq;
    
    for(int i = 0; i < works.size(); i++)
    {
        pq.push(works[i]);
    }
    
    for(int i = 0; i < n; i++)
    {
        int time = pq.top();
        pq.pop();
        time--;
        pq.push(time);
    }
    
    for(int i = 0; i < works.size(); i++)
    {
        int temp = pq.top();
        pq.pop();
        if(temp > 0)
        {
            answer += temp * temp;
        }
    }
    
    return answer;
}

출저

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