[프로그래머스] Level2 : 더 맵게 - C++

문제

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

코딩테스트 연습 - 더 맵게

---

코드

#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> > pq;
    
    for (int i = 0;i < scoville.size(); ++i)
        pq.push(scoville[i]);
    
    while (pq.top() < K && pq.size() > 1)
    {
        int first = pq.top(); pq.pop();
        int second = pq.top(); pq.pop();
        pq.push(first + 2 * second);
        ++answer;
    }
    if (pq.top() < K)
        return -1;
    
    return answer;
}

우선순위 큐를 사용하여 구현하였다. 문제에서 제시한 섞은 음식의 스코빌 지수는 다음과 같다.

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

가장 맵지 않은 음식의 스코빌 지수와 두 번째로 맵지 않은 음식의 스코빌 지수가 필요하므로, 데이터는 오름차순으로 정렬이 되어있어야 편리하다. 따라서 우선순위큐를 오름차순으로 사용하였다.