[Programmers] heap > 더 맵게

힙 - 더 맵게

 

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

코딩테스트 연습 - 더 맵게

priority_queue로 선언한 q를 오름차순으로 정의했고, MIN HEAP과 동일한 형태로 만들었다.
연산에 필요한 첫번째 요소, 두번째 요소는 변수에 각각 저장 후 pop시켜주고, (첫번째 + 두번째 요소*2)를 push해준다.
priority_queue기 때문에 자동으로 오름차순으로 정렬된다.

코드

#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>> q(scoville.begin(), scoville.end());

    while(q.top() < K && q.size() >= 2){

        int top = q.top();
        q.pop();
        int second = q.top();
        q.pop();
        q.push(top + second*2);

        answer++;

    }
    if(q.size() < 2 && q.top() < K ) answer = -1;
    return answer;
}

int main(int argc, const char *argv[])
{

    vector<int> scoville;
    int K = 7;
//    scoville.push_back(1);
//    scoville.push_back(2);
//    scoville.push_back(3);
//    scoville.push_back(9);
//    scoville.push_back(10);
//    scoville.push_back(12);

    scoville.push_back(1);
    scoville.push_back(2);
    K=3;
    
    solution(scoville, K);
    
    return 0;
}