[Programmers] Lv2. 더 맵게 | C++

🔗문제 보러가기

프로그래머스

 

👨‍💻풀이 과정

 

문제 유형도 힙(Heap)이라 분류되어 있었지만, 지문을 읽자마자 최소 힙(Min Heap)이 생각나는 문제였습니다. 입력 범위 숫자가 매우 크므로, 오버플로우만 조심하면 손쉽게 풀 수 있었습니다.

 

✏️소스 코드 및 결과

#include <string>
#include <vector>
#include <queue>
using namespace std;
using LL = long long;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<LL, vector<LL>, greater<LL>> scovilles;
    
    for (const auto element : scoville)
        scovilles.emplace(element);
    

    while (scovilles.size() >= 2) {
        LL leastSpicyFood = scovilles.top();
        scovilles.pop();

        LL secondLeastSpicyFood = scovilles.top();
        scovilles.pop();

        if (leastSpicyFood >= K)
            break;

        LL newScovill = leastSpicyFood + secondLeastSpicyFood * 2;
        answer++;
        scovilles.emplace(newScovill);
    }

    if (scovilles.top() < K)
        return -1;

    return answer;
}