[Programmers] 더 맵게

프로그래머스 - 더 맵게 문제 입니다.

 

문제

우선순위 큐를 이용하여 min heap을 만듭니다.

pop을 두 번 하면 가장 낮은 스코빌 지수 2개를 꺼내올 수 있습니다.

 

문제의 새로운 스코빌을 만드는 공식 대로 계산하여 다시 큐에 넣는 과정을 반복합니다.

최종적으로 큐가 비거나 top의 원소 값이 K 보다 높으면 모든 원소가 K 보다 높다는 것을 보장할 수 있으므로

반복문을 종료합니다. 반복문 종료 후 top이 K 보다 낮다면 -1을 리턴합니다.

 

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

using namespace std;

struct compare {
    bool operator()(int a, int b) {	// min heap
        return a > b;
    }
};

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int i, res = 0;
    priority_queue<int, vector<int>, compare> pq;
    
    for(i = 0; i < scoville.size(); i++) {
        pq.push(scoville[i]);	// 우선 순위 큐에 모두 push
    }
    
    while(pq.top() < K && !pq.empty()) {
        res += pq.top();
        pq.pop();
        if(!pq.empty()) {	// 2개를 뽑을 수 있다면
            res += (pq.top()<<1);	// 제곱 하여 더함
            pq.pop();
            pq.push(res);
            answer++;	// 횟수 증가
        }
        else {
            pq.push(res);
            break;
        }
        res = 0;
    }
    
    if(pq.top() < K) answer = -1;	// top의 원소가 K 보다 낮다면 -1 리턴
    return answer;
}