[프로그래머스 c++] 더 맵게

문제 링크
https://programmers.co.kr/learn/courses/30/lessons/42626

📂 분류

Heap 자료구조

💡 풀이

전형적인 우선순위 큐를 활용해서 푸는 문제다.

주어진 스코빌 지수들 중에서 가장 작은 스코빌과 두 번째로 작은 스코빌을 뽑아 K 이상일 때까지 수행해야 하기 때문에 최소 힙을 이용해서 풀면 된다.

📌 주의할 점

pq의 원소 두 개를 뽑기 때문에 로직을 수행할 때 pq.size()는 2보다 커야 한다.

💻 코드

#include <bits/stdc++.h>

using namespace std;

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