C++ / 프로그래머스 / 더 맵게

문제

 

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

코딩테스트 연습 - 더 맵게

 

문제풀이

 

우선순위 큐를 이용해 풀었다.

먼저 벡터의 값들을 우선순위 큐 pq에 옮긴다.

greater으로 선언하였기 때문에 오름차순으로 알아서 정렬된다.

 

우선순위 큐에서 2개씩 꺼내면서 num1 + num*2 인 값을 우선순위 큐에 집어넣는다.

스코빌 지수가 K이상이 됐다면 반복문을 종료하고 카운트 변수인 answer을 return 한다.

K이상이 되지 않았는데 우선순위 큐가 비었거나 큐가 하나밖에 안 남아있다면 K이상으로 만들 수 없으므로, -1을 return 한다.

 

 

코드

#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>>pq;

    for (int idx = 0; idx < scoville.size(); ++idx) {
        pq.push(scoville[idx]);
    }

    while (!pq.empty()) {
        if (pq.top() >= K) break;
        int num1 = pq.top();
        pq.pop();
        if (pq.empty()) break;
        int num2 = pq.top();
        pq.pop();
        pq.push(num1 + num2 * 2);
        ++answer;
    }

    if (pq.empty()) return -1;
    return answer;
}