[프로그래머스]힙(Heap) : 더 맵게(level 2) (c++)

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

프로그래머스

 

 

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

using namespace std;

int solution(vector<int> scoville, int K) {

    // 최소 힙에 scoville 요소 담기 
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());

    // 힙의 최소값이 K 이상이 되면, 섞은 횟수 반환
    int answer = 0;
    while (!pq.empty() && pq.top() < K)
    {
        // 남은 힙의 요소가 1개이고, 요소 값이 K 미만 일때 : 불가능
        if (pq.size() == 1)
        {
            return -1;
        }

        int min1 = pq.top();
        pq.pop();
        int min2 = pq.top();
        pq.pop();

        pq.push(min1 + min2 * 2);
        ++answer;

    }

    return answer;
}

 

라이브러리를 사용하니 간단하게 끝났다.

최소 힙은 가장 작은 값을 기준으로 트리 정렬되므로,

최소값이 K 이상이면 = 모든 수가 K 이상임을 보장한다.