(프로그래머스 c++)더 맵게

처음 문제를 풀었을 때는 벡터를 이용해서 문제를 풀었다..!

하지만 효율성 테스트에서 시간 초과로 통과하지 못했다..

그래서 priority_queue를 이용하여 문제를 풀었다.

priority_queue는 우선순위 큐로 greater, less 함수를 이용하여 오름차순, 내림차순으로 정렬을 할 수 있다..!

시간 복잡도는 O(logn)이기 때문에 벡터를 이용해 sort 하는 것보다 빠르다..!

 

코드는 어렵지 않으니 천천히 보면 따라갈 수 있다..!

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for(int i = 0; i < scoville.size(); i++)
        pq.push(scoville[i]);
    
    while(pq.top() < K)
    {
        if(pq.size() == 1)
            return -1;
        
        int sum = 0;
        sum += pq.top();
        pq.pop();
        sum += pq.top() * 2;
        pq.pop();
        pq.push(sum);
        answer++;
    }
    return answer;
}