[ 프로그래머스 더 맵게 (Lv2) ] (C++)

프로그래머스의 더 맵게(Lv2) 문제이다.

[ 문제풀이 ]

1) 이 문제는 주어진 음식의 스코빌지수를 K 이상으로 만들어야 하는 문제이다.

   본인은 이 문제를 우선순위 큐를 이용해서 접근해 보았다.

   우선순위 큐는 큐와 동일하게 선입선출의 구조를 가지지만, 큐와 달리 특정 우선순위 순으로 큐 내부에서 순서를

   가지게 된다.

   따라서, 입력으로 주어진 스코빌지수 값들을 우선순위 큐에 오름차순으로 넣어주었다.

   그렇게 되면, 우선순위 큐의 가장 앞에는 스코빌 지수가 가장 작은 값이 들어가 있을 것이다.

   이 후, 순차적으로 큐에서 값을 2개씩 빼내오면서 음식을 섞어준다.

   이 때, 큐에서 가장 위에 있는 값이 K보다 크거나 같다면, 이는 스코빌지수가 가장 작은 음식도 K보다 스코빌지수가

   크다는 이야기 이므로, 계산을 종료시켜주면 된다.

   또한, 2개의 음식을 하나의 음식으로 섞는 과정이기 때문에, 반드시 큐에 남아있는 음식이 2개 이상 되어야 하므로,

   큐의 크기 또한 2 이상일 동안만 탐색을 진행해주면 된다.

[ 소스코드 ]

#include <string>
#include <vector>
#include <queue>
#include <functional>
 
using namespace std;
 
int solution(vector<int> scoville, int K) 
{
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> PQ;
    for(int i = 0 ; i < scoville.size(); i++) PQ.push(scoville[i]);
    
    while(PQ.top() < K && PQ.size() > 1)
    {
        int First = PQ.top();
        PQ.pop();
        
        int Second = PQ.top();
        PQ.pop();
        
        PQ.push(First + (Second * 2));
        answer++;
    }
   
    if(PQ.top() < K) return -1;
    return answer;
}