[프로그래머스] 3단계 - 야근 지수

문제 설명

1시간 동안 작업량 1만큼을 처리할 수 있을때, 야근 피로도를 계산하여 최소화 한 값을 return

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

프로그래머스

 

문제 풀이법

야근 피로도는 남은 일의 작업량을 제곱하여 더한 값이다

문제에서 원하는 것은 야근 피로도를 최소화 한 값이므로 최대한 큰 수를 작게 만들어서 제곱 시에 값이 커지는 것을 막는게 핵심이다

 

따라서 우선순위 큐를 사용하여, 항상 값을 내림차순으로 정렬하도록 한다

작업량이 다 끝날 때까지, 즉 n이 0이 될 때까지 우선순위 큐의 top의 값을 1개씩 줄여주도록 구현했다

 

예를 들어 [4, 3, 3]있고 n이 4라면

- n = 4 -> [3, 3, 3]

- n = 3 -> [3, 3, 2]

- n = 2 -> [3, 2, 2]

- n = 1 -> [2, 2, 2]

이런식으로 계산되므로 야근 피로도는 최소가 될 수 있다

 

만일 우선순위 큐의 top이 0이라면 남은 작업량이 없는 것이므로 바로 return 0 해준다

 

 

소스 코드

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

using namespace std;

bool cmp(int a, int b) {
    return a > b;
}

long long solution(int n, vector<int> works) {
    long long answer = 0;
    
    priority_queue<int, vector<int>> q;
    
    for (int i = 0; i < works.size(); i++)
        q.push(works[i]);
    
    while (n != 0 && !q.empty()) {
        int value = q.top();
        q.pop();
        if (value == 0)
            return 0;
        
        q.push(value - 1);
        n--;
    }
    
    while (!q.empty()) {
        int value = q.top();
        q.pop();
        
        answer += value * value;
    }
    
    return answer;
}