프로그래머스 - 더 맵게

 코딩테스트 고득점 Kit의 힙에서 Level 2단계 문제인 더 맵게이다. 우선순위 큐를 이용한 아주 기초적인 문제였다. 기억해야 할 점은 C++ STL 에서 priority_queue는 디폴트로 최대 힙이다. 따라서 최소 힙으로 만들기 위해서는 priority_queue<int, vector<int>, greater<int>> pq; 와 같이 선언해야 한다.

 

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

using namespace std;

int makeScoville(vector<int>& scoville, int k)
{
    int result = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    
    for (int i = 0; i < scoville.size(); i++)
    {
        pq.push(scoville[i]);
    }
    
    while (true) 
    {
        if (pq.size() >= 2)
        {
            int temp1 = pq.top();
            pq.pop();
            int temp2 = pq.top();
            pq.pop(); 
        
            if (temp1 >= k)
            {
                break;
            }
        
            int temp = temp1 + (temp2 * 2);
            pq.push(temp);
            result++;
        }
        else {
            break;
        }
    }
    
    if (pq.top() < k)
    {
        return -1;
    }
    else
    {
        return result;
    }
}
    
int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    answer = makeScoville(scoville, K);
    
    return answer;
}