[42626] 더 맵게 ⭐⭐

https://school.programmers.co.kr/learn/courses/30/lessons/42626
난이도 ⭐⭐

문제

---

나의 풀이

처음엔 단순하게 vector와 sort를 이용해서 처리하려고 했는데, 그랬더니 효율성에서 다 실패하고 말았다.
그래서 삽입된 요소들을 내부에서 정렬해주는 우선순위 큐를 사용했다.

#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>> queue(scoville.begin(), scoville.end());

    // 스코빌 지수를 K 이상으로 만들기 위해 음식을 섞어야 하는 횟수를 구하는 것  
    //섞은 음식의 스코빌 지수 = 가장 맵지 않은 음식의 스코빌 지수 + (두 번째로 맵지 않은 음식의 스코빌 지수 * 2)  

    // queue 안에 원소가 2개 이상 있을 때,
    // 제일 첫 원소가 K 보다 작다면 (크면 섞을 필요 X)
    while (queue.size() > 1 && queue.top() < K)
    {
        int first = queue.top();
        queue.pop();

        int second = queue.top();
        queue.pop();

        queue.push(first + (second * 2));
        answer++;
    }

    // 위의 반복문을 돌았다는 가정하에 queue 안에 원소가 남아있고, 첫 원소가 K보다 작다면  
    // 아무리 섞어도 K이상 만들 수 없다는 것으로 판단하여 -1 반환  
    if (queue.size() > 0 && queue.top() < K)
    {
        return -1;
    }

    return answer;
}