[Level_2] 더 맵게 (C++)

<priority_queue> 자료구조

---

해당 문제는 priority_queue 를 알면 쉽게 풀 수 있다. 

값을 삽입 할 때 오름차순으로 정렬 되어있는 min heap으로 생성해준다. 

그렇게 한다면 최소값이 루트노드에 위치하게 되며 제일 작은 값을 우선적으로 pop을 해주기 때문에 해당 문제를 쉽게 풀 수 있다. 

#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>> q; 
    for(int x : scoville){
        q.push(x); 
    }
    int cnt =0; 
    while(!q.empty()){
        int a = q.top(); 
        if(a>=K)return cnt; 
        cnt++; 
        q.pop(); 
        if(q.empty())return -1; 
        int b= q.top(); 
        q.pop(); 
        a = a+ 2*b; 
        q.push(a);         
    }    
    return cnt;
}

 

코딩테스트 연습 - 더 맵게