프로그래머스(C++) - 더맵게

●문제

 

●입출력

 

문제풀이 : scoville지수가 K보다 낮으면 가장 낮은 경우 낮은음식은 

가장낮은 음식 스코빌지수 + (두번째로 낮은 음식 스코빌지수 * 2) 해준값을 해준다

모든 음식의 스코빌지수가 k 이상이 될떄까지 반복 하고 반복한 횟수 count

 

풀이 알고리즘 : heap / priority_queue 최소힙

 

푼방법 : 최소힙 트리를 만들고 힙의 루트노드 < K가 될때까지 반복

최소힙에서 .pop()을 두번해주고  answer++ 해주면 결과도출

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

using namespace std;

int solution(vector<int> scoville, int K) 
{
    int answer = 0;
    //최소힙
    priority_queue<int, vector<int>, greater<int>> minPQ;
    for (int i : scoville)
    {
        //힙에 추가
        minPQ.push(i);
    }

    //가장 루트노드가 k이상이 될떄까지 반복
    while (minPQ.top() < K)
    {
        //만약 섞을게 2개 미만이면 실패
        if (minPQ.size() < 2)
        {
            return -1;
        }
        //첫번째 루트노드 지우기
        int rootNodeFirst = minPQ.top();
        minPQ.pop();
        //두번째 루트노드 지우기
        int rootNodeSecond = minPQ.top();
        minPQ.pop();
        //섞은 음식의 스코빌지수 음식 힙에 다시 넣기
        minPQ.push(rootNodeFirst + (rootNodeSecond * 2));
        //섞은수 증가
        answer++;
    }
    return answer;
}