[프로그래머스] 더 맵게

문제

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

접근 방법

priority_queue를 이용했다.
std::greater<int>를 이용해 오름차순 정렬을 하여, 가장 안 매운 순서대로 정렬되게 하였다.
가장 안매운 음식이 K 미만이라면
1번째, 2번째 안매운 음식을 pop해서 섞은 후 push함을 반복하였다.

풀이

#include <string>
#include <vector>
#include <iostream>
#include <queue>
#include <algorithm>
#include <deque>

using namespace std;



int solution(vector<int> scoville, int K) {
    int answer = 0;
        
    // 오름차순 priority_queue
    priority_queue<int, deque<int>, greater<int>> pq;
    
    for(int s : scoville)
    {
        pq.push(s);    
    }
        
    while(pq.size() > 1)
    {
        // 가장 안매운 음식의 스코빌 지수가 K 이상인지 
        if (pq.top() >= K)
            break;
        
        // 가장 안매운 음식
        int a = pq.top();
        pq.pop();
        
        // 2번째로 안매운 음식 
        int b = pq.top();
        pq.pop();
        
        // 섞기
        pq.push(a + (b * 2));
        
        // 섞은 횟수 증가
        answer++;
    }
    
    // 가장 안매운 음식의 스코빌 지수가 K 이상이 안된다면 
    if (pq.top() < K) answer = -1;
    
    return answer;
}

정리

priority_queue를 라이브러리 안보고 잘 생성할 수 있게 하기