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

문제 출처: https://programmers.co.kr/learn/courses/30/lessons/42626

문제 난이도

Lv 2

문제 접근법

힙을 이용한 문제이므로 힙 = 우선순위 큐
기본적으로 우선순위 큐는 최대힙(모든 부모노드들이 자식노드들보다 큰값을 가지는것) 이므로
이 문제에서는 최소힙으로 바꿔서 풀었다.

최소힙으로 바꿀때 따로 operator이나 값을 넣을때 -를 붙이고 넣어도 되지만, 나는 greater<int>를 이용했다.

greater < int >는 vector container sort로 내림차순을 나타낸다. 하지만 우선순위 큐에서는 최소힙으로 나타낸다.

추가 라이브러리
queue

통과 코드

#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(scoville.begin(), scoville.end());
    
    while(1){
        int first = pq.top();
        pq.pop();
        if(first >= K) break;
        else if(pq.empty()){
            answer = -1;
            break;
        }
        int second = pq.top();
        pq.pop();
        int result = first + (second * 2);
        pq.push(result);
        answer++;
    }
    return answer;
}

피드백

사실 예전에 풀었던 문제인데 한달만에 다시 알고리즘을 풀려고 하니깐 쉬운 문제도 버벅이길래 다시 정리할겸 풀었다.