[c++] 더 맵게 (프로그래머스 - heap/ priority queue)

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

코딩테스트 연습 - 더 맵게

 

min heap 선언방법 기억해두고

vector<int, vector<int>, greater<int>> min_heap;

벡터나 배열은 선언시 바로 값 대입 가능!

push 하면 자동으로 정렬가능

 

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

using namespace std;

// min heap을 통해 구현
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    priority_queue<long long, vector<long long>, greater<long long>> minHeap(scoville.begin(), scoville.end());
    
    while (1) {
        if (minHeap.top() >= K) {
            break;
        }
        if ((int)minHeap.size() < 2) {
            answer = -1;
            break;
        }
        long long nonSpicy = minHeap.top();
        minHeap.pop();
        
        long long nonSpicy2 = minHeap.top();
        minHeap.pop();
        
        long long newSpicy = nonSpicy + (2 * nonSpicy2);
        minHeap.push(newSpicy);
        answer++;
    }
    
    return answer;
}