[프로그래머스] Level2 - 더 맵게 (C++)

https://programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

[풀이] 우선순위 queue

 

시간복잡도 : O(nlgn)

 

 

#include <cstdio>
#include <queue>
#include <vector>
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
 
    priority_queue<int> pq;
    for (int& t : scoville) pq.push(-t);
    
    while (!pq.empty()) {
 
        if (-pq.top() >= K) return answer;
        if (pq.size() <= 1) return -1;
 
        int a = -pq.top(); pq.pop();
        a += -2 * pq.top(); pq.pop();
 
        pq.push(-a);
 
        answer++;
    }
    return answer;
}

https://github.com/has2/Algorithm/blob/master/programmers/level2/%EB%8D%94%20%EB%A7%B5%EA%B2%8C.cpp