프로그래머스_더맵게

이번에 포스팅할 문제는 프로그래머스에 있는 더맵게 라는 문제입니다.
문제링크 :https://programmers.co.kr/learn/courses/30/lessons/42626
음식들의 맵기 정도를 담은 scoville의 길이가 최대 1,000,000가 들어올 수 있기 때문에 시간복잡도는 O(NlogN)안에 속하는 알고리즘으로 풀어야 할거 같습니다.
처음에는 scoville의 값이 벡터값으로 들어오기 때문에, sort를 사용해, 오름차순으로 정렬해 해결할까? 고민했지만, 그렇게 하는것 보다,우선순위 큐를 사용해서 풀도록 했습니다.
우선순위 큐를 사용한 이유는 우선순위 큐를 이용하면 삽입 삭제가 빠르고, 섞은 음식의 스코빌 지수를 넣고 섞기 전 음식들의 스코빌 지수를 다루기 쉬울거 같아서 입니다.

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

//구조체 정의
//오름차 정렬용
struct qu{
    
    int score;
    
    qu(int a){
        score=a;
    }
    bool operator<(const qu & b) const{
        return score>b.score;
    }
    
    
};


int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<qu> pq;
    
    //스코빌 지수를 우선순위 큐에 넣는다.
    for(int i=0;i<scoville.size();i++){
        pq.push(scoville[i]);
    }
    
    //우선순위 큐가 비지 않고, 우선순위 큐의 가장 위 즉 가장 작은 값이 K보다 작을때 까지만 진행
    while(!pq.empty()&&pq.top().score<K){
        int first;
        int second;
        int make;
        
        
        first=pq.top().score;
        pq.pop();
        
        //뒤에 뺄 수가 없다면
        //첫번째 스코빌 값만 존재할때,
        //뒤에 뺄 값이 없으면 종료한다
        if(pq.empty()){
            pq.push(first);
            break;
        }
        second=pq.top().score;
        pq.pop();
        
        //음식을 섞기
        make=(first+second*2);
        pq.push(make);
        answer++;
    }
    
    //모든 음식을 k이상의 스코빌 지수로 만들지 못한경우 
    if(pq.top().score<K){
        answer=-1;
    }
    
    //모든 음식을 k이상의 스코빌 지수로 만든경우
    return answer;
}