더 맵게 C++

문제 설명

입출력 예

scoville                                                                                                                                        K                         return

[1, 2, 3, 9, 10, 12]

7

2

입출력 예 설명

1. 스코빌 지수가 1인 음식과 2인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 1 + (2 * 2) = 5
   가진 음식의 스코빌 지수 = [5, 3, 9, 10, 12]
2. 스코빌 지수가 3인 음식과 5인 음식을 섞으면 음식의 스코빌 지수가 아래와 같이 됩니다.
   새로운 음식의 스코빌 지수 = 3 + (5 * 2) = 13
   가진 음식의 스코빌 지수 = [13, 9, 10, 12]

모든 음식의 스코빌 지수가 7 이상이 되었고 이때 섞은 횟수는 2회입니다.

 

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = -1;
    priority_queue<int, vector<int>, greater<int>> pq;    
    
    for(int i=0; i<scoville.size(); i++)
    {
        pq.push(scoville[i]);
    }
    
    int cnt =0;
    while(!pq.empty())//비어있거나 
    {
        if(pq.top() > K ||pq.size() <2)break;
        cnt ++;
        int lowest = pq.top();
        pq.pop();
        lowest = lowest + (pq.top()*2);
        pq.pop();
        pq.push(lowest);
    }
    if(pq.top() < K)return answer;
    else 
    {
        answer = cnt; 
        return answer;
    }
}

 

=> 우선순위 큐를 이용하여 풀어야 하는 문제입니다. 

=> 해당문제에서는 더 낮은 맵기의 숫자들이 맨 위에 있어야 하므로, 최소 힙(MIN HEAP)을 사용하여야 합니다. 

=> 우선순위 큐에 대한 정리는 이후에 진행해보도록 하겠습니다. 

=> pq(MIN HEAP)은 넣는 순서와 상관없이 가장 작은 수가 맨 위에 위치하게 됩니다. 

=> 이를 이용해 맨 위에 있는 숫자와 POP() 한 후에 맨위에 있는 숫자를 통해 새로운 맵기의 음식을 생성하여 pq에 PUSH 합니다. 

=> 이러한 과정을 진행하며 모든 경우를 진행했음에도 불구하고 K를 넘지 못하는 경우와 pq SIZE가 2이하인 경우를 예외처리해주어야 합니다.