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

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int want = 0;
    priority_queue<int, vector<int>, greater<int>> pq;  //낮은 순으로 정렬하기 위해 pq
    
    for(int i = 0; i < scoville.size(); i++)    //스코빌 지수 넣기
        pq.push(scoville[i]);
    
    if(pq.top() >= K) return 0; //가장 작은 수가 k이상일 때 바꿀 필요가 없다.
    
    while(pq.size() > 1)    //한개 이하일 경우 조합을 할 수 없다.
    {
        //처음 수와 두번째로 낮은 수를 조합한다.
        int one = pq.top();
        pq.pop();
        int two = pq.top();
        pq.pop();
        
        want = one + (two * 2);
        answer++;   //조합했으니 카운트증가
        
        pq.push(want);
        
        if(pq.top() >= K) break;    //조합한 후 가장 작은 수가 k이상일 경우 break
    }
    
    if(want < K) return -1; //무조건 마지막으로 조합한 수가 남게 되므로 그것이 k보다 작으면 불가능한 것
    
    
    return answer;  //조합한 횟수
}

 

풀이

1. 힙으로 구성되어 있는 priority_queue를 사용하여 문제를 푼다.
2. 낮은 순으로 정렬한다. <int, vector<int>, greater<int>> 낮은순으로 정렬된 큐
3. 새로운 음식을 조합해도 그것이 제일 낮은 수가 아닐  수도 있기에 조심
4. 조합한 것을 pq에 넣어준다. 이때 조합했으니 조합 횟수를 추가
5. 그중에 제일 낮은 수가 k를 넘을 경우 모두 k보다 높은 것임
6. 모두 조합을 했음에도 불구하고 조합한 최종값이 k보다 작을 경우 k이상으로 못만드므로
   -1을 리턴해준다.
7. 아닐 경우 조합한 횟수를 넣어준다.