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

 

 

 

 

 

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

프로그래머스

 

이번 문제는 힙(Heap) 문제였습니다.

스코빌 지수가 가장 낮은 두 개의 음식을 섞어야 하므로 오름차순으로 정렬되는 우선순위 큐를 사용했습니다. 🙂

 

 

 

 

 

📝 문제 풀이

1. 우선순위 큐 pq의 정렬 조건을 오름차순으로 지정

2. 모든 음식을 pq에 삽입

3. 스코빌 지수가 가장 낮은 음식 2개를 섞어서 pq에 삽입 (pq의 사이즈가 2보다 작을 때까지 반복)

4. 모든 음식의 스코빌 지수를 K 이상으로 만들지 못했다면 -1 반환

 

 

 

 

👩🏻‍💻 C++ 코드

#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.size() >= 2 && pq.top() < K) {
        int firstMin = pq.top();
        pq.pop();
        
        int secondMin = pq.top();
        pq.pop();
        
        answer++;
        pq.push(firstMin + secondMin * 2);
    }
    
    // 큐에 남아있는 음식의 스코빌 지수가 K보다 작은 경우
    if (!pq.empty() && pq.top() < K) return -1;
    return answer;
}

 

프로그래머스 - 결과 화면