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

안 매운 음식들을 섞어서 매운 음식으로 만들건데

총 몇 번 섞어야 하는지 구하는 문제

 

---

문제의 조건

 

1. 음식들의 맵기를 담은 배열 scoville, 기준이 되는 스코빌 지수 K가 주어짐

 

2. scoville 원소들이 K 이상 되어야 함

 

3. 새로운 음식을 만드는 공식은

이렇다. 

가장 덜 매운 두가지를 뽑아서 위의 공식으로 섞는다. 

 

4. 모든 음식을 K 이상으로 만들 수 없으면 -1 리턴 (이 예외처리를 안 해서 또 시간 날림 ㅠ.ㅠ 문제를 똑바로 읽읍시다...)

 

5. 가장 덜 매운 음식의 지수가 최소 K 이상 되려면 몇 번 섞어야 하는지 구해서 리턴하기 

 

---

원소 하나하나 복사해서 set으로 만든다고 뻘짓했는데 우선순위 큐로 쉽게 해결할 수 있었던 문제...

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    //우선순위 큐 만듦
    priority_queue<int, vector<int>, greater<int>> newScovilles(scoville.begin(), scoville.end());

    int newScoville = 0;
    int answer = 0;
    //큐에 조합한 scoville이 1개 남을 때까지 반복 
    while (1 < newScovilles.size() && K > newScovilles.top())
    {
        //큐에서 첫번째랑 두번째 원소 추출
        int first = newScovilles.top();
        newScovilles.pop();
        int second = newScovilles.top();
        newScovilles.pop();
        
        //새 scoville 계산 후 큐에 삽입 
        newScoville = first + (second * 2);
        newScovilles.push(newScoville);
        answer++;
    }

    //만약 큐의 첫번째 원소가 K보다 작으면 -1 리턴 
    if (K > newScovilles.top())
        return -1;

    return answer;
}