APS/프로그래머스

[힙(Heap)] 더 맵게

문래동까마귀 2022. 1. 4. 17:21

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

 

코딩테스트 연습 - 더 맵게

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같

programmers.co.kr

#include <string>
#include <vector>
#include <iostream>
#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]);
    }

    int cnt = 0;
    while (1) {
        if (pq.size() == 1 && pq.top() < K)
            return -1;

        if (pq.top() > K)
            break;

        int pq1 = pq.top();
        pq.pop();
        int pq2 = pq.top();
        pq.pop();

        int tmp = pq1 + (pq2 * 2);

        pq.push(tmp);
        cnt++;
    }

    answer = cnt;
    return answer;
}

int main() {

    cout << solution({ 1, 2, 3, 9, 10, 12 }, 7);//	2

    return 0;
}