[프로그래머스] [C++] 더 맵게 (queue, heap)

1. 문제

모든 음식의 스코빌 지수를 K 이상으로 만들어야한다.

 

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

 

모든 음식의 스코빌 지수가 K 이상이 될 때까지 반복하여 섞는다.

 

섞으면 새로운 음식이 된다.

 

가장 작은 섞는 횟수를 구하여라

 

2. 우선순위 큐- 힙

우선순위 큐로 가장 작은것을 골라낼 수 있다.

 

 

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int> pq;
    
    for(int i = 0; i < scoville.size(); i++)
        pq.push(-scoville[i]);
    while(pq.size() != 1)
    {
        int small1 = -pq.top(); pq.pop();
        int small2 = -pq.top(); pq.pop();
        if(small1 >= K)
            break;
        pq.push(-(small1 + (small2*2)));
        answer++;
    }
    if(-pq.top() < K)
        answer = -1;
    
    return answer;
}

programmers.co.kr/learn/courses/30/lessons/42626