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

코딩테스트 연습 - 야근 지수 | 프로그래머스 스쿨

프로그래머스

문제는 위에 링크에 나와있고, 문제 이해를 하는데 오래걸렸다.

 

문제해설

문제는 works 배열이 [4, 3, 3] 다음과 같으면 n이 4면 큰 값부터 -1을 해서 1번째 [3, 3, 3] 2번째 [3, 3, 2] 3번째 [3, 2, 2] 4번째 [2, 2, 2] 이런식으로 빼주고 배열을 제곱한 값이 2^2 + 2^2 + 2^2 = 12가 되는 문제였다. 코드는 아래와 같다 처음에 그냥 정렬로 풀었더니 효율성에서 안풀려서 우선순위큐로 해결했다.

 

#include <string>
#include <vector>
#include <iostream>
#include <queue>
using namespace std;
long long solution(int n, vector<int> works) {
    long long answer = 0;
    priority_queue<int> queue;
    for (int i = 0; i < works.size(); i++)
    {
        queue.push(works[i]);
    }
    while (n--)
    {
        int temp = queue.top();
        temp = temp - 1;
        if(temp < 0)
            temp = 0;
        queue.pop();
        queue.push(temp);
    }
    while (!queue.empty()) {
        answer += queue.top() * queue.top();
        queue.pop();
    }
    
    return answer;
}