우선순위 큐 이용한 문제 ㅋㅋ

출처

프로그래머스

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

• 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다.

#include <iostream>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> pq; // 우선순위 큐 | Min Heap
    // priority_queue<int, vector<int>, greater<int> > pq; // 우선순위 큐 | Max Heap
    int answer = 0;
    int n1, n2;
    
    for(auto n : scoville) 
        pq.push(n); // Min Heap의 우선순위 큐에 모두 때려 넣는다 -> 스코빌 지수가 작은 녀석들부터 순서대로 튀어나온다
    
    while(pq.size() > 1 && pq.top() < K) // 큐에 2개 이상 들어가야만 세그멘테이션 폴트 에러가 발생하지 않는다.
    {
        // 두 개를 뽑고,
        n1 = pq.top(); pq.pop();
        n2 = pq.top(); pq.pop();
        
        // 두 음식을 섞어서 새롭게 스코빌 지수를 하나 탄생시키고 넣으면
        pq.push(n1+n2*2); // 해당 힙에 구조가 조정되어 들어간다 -> Min Heap 계속 유지하기 때문에 top이 K 이상이라면 나머지 값들도 모두 K이상을 만족
        answer++;
    }
    
    if(pq.top() < K) // 위 과정을 거쳤는데도 K 이상을 충족하지 않는다면
        return -1; // 더 이상 조합으로는 K 이상으로 맞출수 없다는 소리이다. 음식이 1개 남았고, K미만인 경우임.
    
    return answer;
}