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

문제 URL

https://school.programmers.co.kr/learn/courses/30/lessons/42626

프로그래머스

[문제]

가진 음식의 스코빌 지수를 담은 배열 scoville과 원하는 스코빌 지수 K가 주어질 때, 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성하라.

 

[문제 풀이]

이 문제는 우선순위 큐를 사용하는 문제이다. 오름차순 우선순위 큐를 통해 맨 앞의 두 스코빌 지수를 섞어 새로운 스코빌 지수를 계산한 뒤 다시 push 해주는데, 이 과정을 맨 앞 원소가 K 이상이 될 때까지 반복해 주면 된다.

---

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq(scoville.begin(), scoville.end());  // 오름차순 정렬 
    
    while(pq.size() > 1 && pq.top() < K) {
        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;
}