📒활용개념

Priority_queue를 활용하여 Queue의 특성과 Sorting의 장점을 모두 활용한다.

📌문제설명

매운 것을 좋아하는 Leo는 모든 음식의 스코빌 지수를 K 이상으로 만들고 싶습니다. 모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 Leo는 스코빌 지수가 가장 낮은 두 개의 음식을 아래와 같이 특별한 방법으로 섞어 새로운 음식을 만듭니다.

섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)

모든 음식의 스코빌 지수를 K 이상으로 만들기 위해 섞어야 하는 최소 횟수를 return 하도록 solution 함수를 작성해주세요.

주어진 수학 식을 따라 문제를 풀면서 가장 작은 스코프 지수부터 해결을 한다.
-> 여기서 sorting을 사용한다.

📌구현

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

//sort알고리즘 사용보다 priority_queue 사용이 시간복잡도 측면에서 훨씬 유리하다.
 
using namespace std;
 
int solution(vector<int> scoville, int K) {
    int answer = 0;
    //vector에 오름차순으로 정렬하여 넣은 queue
    priority_queue<int, vector<int>, greater<int> > scov(scoville.begin(), scoville.end());
    
    //가장 작은 스코빌 지수가 k이상이라면 정지.
    while (scov.top() < K) {
    	//queue의 크기가 1이라면 더이상 섞을 수 있는 음식이 없어서 종료.
        if(scov.size()==1){
            return -1;
        }
        int first = scov.top();
        scov.pop();
        int second = scov.top();
        scov.pop();
        //새로운 음식의 스코빌 지수를 삽입+정렬
        scov.push(first + (second * 2));
        answer++;
    }
    return answer;
}

처음에는 일반 queue를 사용하여 새로운 음식을 만들 때 마다 sorting을 했지만, 시간복잡도에서 걸려서 다시 Priority_Queue를 사용하였다.

📌주의점

• 시간복잡도 측면에서 sort보다 priority queue 사용이 더 유리하다.
• 주어진식을 잘 따라가면서 만들 수 없는 경우를 생각하면 풀기 쉬운 문제다.