더 맵게

문제 링크 => 코딩테스트 연습 - 더 맵게 | 프로그래머스 (programmers.co.kr)

코딩테스트 연습 - 더 맵게

---

전형적인 Heap 문제이다.

 

priority_queue 를 이용하여 최소힙으로 가장 작은 값과 두번째로 작은 값을 가져와서 연산을 해준다.

 

이러한 과정을 계속하다가 힙에 담겨진 가장 작은 값이 K보다 크거나 같아지는 경우는 counting 한 결과값을 반환하면 된다.

 

모든 연산이 끝나고 Heap size가 1이 되는 경우 이 또한 K보다 크거나 같아지는 경우에 counting 한 결과값을 반환하고 그 외에 -1을 반환하면 된다.

 

풀이 Code

 

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

using namespace std;

int solution(vector<int> scoville, int K) {    
    int result = 0;
    priority_queue<int> pq;
    for(int i=0; i<scoville.size(); i++) pq.push(-scoville[i]);
    while(pq.size() >= 2){
        int first = -pq.top(); pq.pop();
        if(first >= K) return result; 
        int second = -pq.top(); pq.pop();
        pq.push(-(first + second * 2));
        result++;
    }
    
    if(-pq.top() >= K) return result;
    return -1;
}