[Lv 2] 더 맵게

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

프로그래머스

 

최소 스코빌 계수인 K 이상으로 배열의 요소를 만들어야한다.

이때 가장 작은 스코빌 계수인 음식과 두번째 작은 스코빌 계수 음식을 섞을 수 있다.

 

따라서 가장 작은 스코빌 계수 음식과 두번째 작은 음식을 찾기 위해 우선순위 큐를 사용했다.

큐의 top에 존재하는 음식이 K보다 작은 경우 음식을 섞어야한다.

이때 큐가 비어있는 경우 음식을 더이상 섞을 수 없으므로 -1을 반환한다.

 

반복을 빠져나오면 음식을 섞어서 K이상으로 배열을 완성했기 때문에 answer을 그대로 반환한다. 

 

#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#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 i = 0;i<scoville.size();i++)
        q.push(scoville[i]);
    
    while(!q.empty()){
        int food1 = q.top();
        q.pop();
        if(food1 < K){
            if(q.empty())
                return -1;
            
            int food2 = q.top();
            q.pop();
            q.push(food1 + (food2 * 2));
            answer++;
        }
        else{
            break;
        }
    }

    return answer;
}