프로그래머스 - 야근 지수(C++)

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/12927

문제 난이도

Lv 3

문제 접근법

제일 큰 값을 계속 작게 만들어 숫자 간 차이가 없어야 가장 작은 최소값이 된다.

통과 코드

#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> pq;
    for(int i=0; i<works.size(); i++){
        pq.push(works[i]);
    }
    while(n--){
        if(pq.empty()) break;
        int top = pq.top();
        pq.pop();
        top--;
        if(top>0) pq.push(top);
    }
    while(!pq.empty()){
        long long tmp = pq.top() * pq.top();
        pq.pop();
        answer += tmp;
    }
    
    return answer;
}

피드백

처음엔 우선순위큐를 생각하지 못하고 vector에 넣어 계속 sort해줄 생각을 했다. 근데 너무 시간초과가 날 것같아 생략하고 구현했는데 많은 테케 중에 7개만 통과 했다. 우선순위큐를 더 다양하게 활용할 수 있다는 걸 염두하자!