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

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

프로그래머스

 이 문제를 풀며 생각의 순서는 이러했다.

1. 내가 잘 하는 문제 유형으로 바꿀 수 있을까? dfs, bfs 등등

2. 아니라면 뭘로 바꿀 수 있을까. 이 문제는 우선 가장 최소화 시키는 것이 목적이다. 그리고 n이 백만으로 크다. 그렇다면 DP, 이분탐색, 파라메트릭을 사용할 수 있을까?

3. 모두 아닌 것 같은데 그렇다면 단순 구현인가? 

4. 단순 구현이라 하면 어떤 자료구조를 사용할 수 있을까.

 

그리고 정렬하여 찬찬히 n을 줄여나가는 것을 생각해냈는데 그럼 n번의 정렬이 필요하고 이는 시간초과가 날 것이 뻔했다. 그리고 우선순위큐가 생각나 우선순위큐로 해결했다. 우선순위큐를 사용하면 O(nlongm) 으로 해결가능하다. n은 n번 반복해야하고 logm 은 우선순위 큐 자체의 시간복잡도이다. 

 

#include <string>
#include <vector>
#include <queue>
using namespace std;

priority_queue<int> pq;

long long solution(int n, vector<int> works) {
    long long answer = 0;
    
    for(auto a : works)
        pq.push(a);
    
    while(n > 0){
        int tmp = pq.top();
        pq.pop();
        if(tmp - 1 > -1)
            pq.push(tmp - 1);
        n--;
        if(pq.empty())
            break;
    }
    
    while(!pq.empty()){
        answer = answer + pq.top() * pq.top();
        pq.pop();
    }
    
    return answer;
}