[프로그래머스] 힙(Heap) - 더 맵게, C++

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

코딩테스트 연습 - 더 맵게 | 프로그래머스

 본 문제는 pripriority_queue를 이용하는 문제다. pripriority_queue는 max_heap, min_heap으로 구현 할 수 있다. 여기서 priority_queue 사용법을 간단히 설명하자면

• min_heap : priority_queue<int, vector<int>, greater<int>> pq;
• max_heap : priority_queue<int, vector<int>, less<int>> pq; 이다. heap에 대해 자세한 설명은 생략한다.

코딩 절차는 다음과 같다.

1. 가장 맵지 않은 음식의 스코빌 지수 구하기
2. 두 번째로 맵지 않은 음식 스코빌 지수 구하기
3. 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)를 구하여 heap에 저장하기
4. heap의 모든 값이 기준 값 이상이 될 때 까지 반복

#include <string>
#include <vector>
#include <queue>
 
using namespace std;
 
int solution(vector<int> s, int k) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq;
    for (int i = 0; i < s.size(); i++) {
        pq.push(s[i]);
    }
    while (true) {
        // 모든 값이 기준 값 이상일 경우
        if (pq.top() >= k) break;
        // 스코빌 지수 구하기
        if (pq.top() < k) {
            int x = pq.top();
            pq.pop();
            int y = pq.top();
            pq.pop();
            int tmp = x + (y*2);
            pq.push(tmp);
            answer += 1;
        }
        if (pq.top() < k && pq.size() == 1) {
            answer = -1;
            break;
        }
    }
    return answer;
}