Level 2. 더 맵게

Level 2. 더 맵게

 

 

최소 힙을 유지하는 우선순위 큐를 활용해 작은 수부터 뽑아내 해결했다.

 

K보다 작은 지수가 마지막 1개 남았으면 성공할 수 없다는 뜻이다.

 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K)
{
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> prQue(scoville.begin(), scoville.end());

    while (prQue.top() < K)
    {
        if (prQue.size() == 1)
            return -1;

        int smallest = prQue.top(); prQue.pop();
        int second   = prQue.top(); prQue.pop();

        prQue.emplace(smallest + second + second);
        ++answer;
    }

    return answer;
}