[프로그래머스] 더 맵게

이 포스트는 프로그래머스 사이트의 더 맵게 문제 풀이입니다.

문제

해결 과정

이 문제는 C++ 의 힙 자료구조를 활용해서 해결할 수 있습니다.

C++ STL 의 우선순위 큐는 기본적으로 최대 힙을 사용하지만, greater<> 함수를 넘겨줌으로서
최소 힙처럼 사용할 수 있습니다.

그리고 문제의 설명처럼 2가지 음식이 존재할 때 섞는 행동이 가능하므로
첫 번째 pop() 호출 후 비어있는지 또한 확인해야 합니다.

위 2가지를 고려하면 쉽게 해결할 수 있습니다.

제출 코드

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

using namespace std;

int solution(vector<int> scoville, int K) {
    priority_queue<int, vector<int>, greater<int>> q;
    for(int s : scoville) {
        q.push(s);
    }
    
    int answer = 0;
    while(q.empty() == false) {
        int first = q.top();
        q.pop();
        
        if(first >= K) {
            return answer;
        }
        else if(false == q.empty()) {
            int second = q.top() * 2 + first;
            q.pop();
            q.push(second);
            answer += 1;
        }
    }
    return -1;
}

제출 결과