[c++/알고리즘] 프로그래머스 더맵게(heap)

corncheese·2021년 8월 20일
0

알고리즘문제풀이

목록 보기
31/31

heap->priority_queue를 사용하여 풀이한다.
https://programmers.co.kr/learn/courses/30/lessons/42626

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int first, second;
    priority_queue<int> pq; // 내림차순 자동 정렬
    // priority_queue 오름차순 정렬
    //priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());
    
    // 오름차순으로 정렬하기 위해 -를 곱하여 push한다.
    for(int i=0; i<scoville.size(); i++){
        pq.push(-scoville[i]);
    }
       
    while(-(pq.top()) < K){
        //pq에 1개 남았을 경우, 더이상 k이상의 수를 만들 수 없으므로 answer = -1
        if(pq.size()==1){ answer = -1; break;}
        
        first = -(pq.top());
        pq.pop();
        second = -(pq.top());
        pq.pop();
        
        pq.push(-(first+(second*2)));
        answer++;        
    }
    
    return answer;
}

0개의 댓글