코딩테스트 : 더 맵게(priority_queue)

해당 문제는 scoville에 있는 모든 원소가 K보다 크게 만드는 문제로 두 개의 음식을 섞으면 맵기가 높아진다는 규칙을 이용해서 풀어야한다.

섞은 음식의 스코빌 지수 = 가장 안 매운 음식 + (두 번째 안 매운 음식 * 2)

때문에 vector내에 원소에서 가장 작은 값과 두 번째 작은 값을 빠르게 꺼낼 수 있어야하며, 섞은 음식도 정렬해서 넣어야한다.

내가 떠오른 방법은 priority_queue를 이용하는 것이다.

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    
    //우선순위 큐를 만들어준다. greater<int>를 추가해 내림차순으로 정렬한다.
    priority_queue<int, vector<int>, greater<int>> q;
    //scoville vector를 priority_queue로 옮기며 정렬해준다.
    for(int i : scoville)
    {
        q.push(i);
    }
    
    //가장 위에 수(가장 작은 수)가 K보다 크거나 같으면 모든 수가 K보다 크거나 같은 특징
    
    //가장 작은 수가 K보다 작다면 섞기 진행
    while(q.top() < K)
    {
		    //만약 크기가 2보다 작으면 섞을 수 없으니 -1 반환
        if(q.size() < 2)
            return -1;
        
        //가장 작은 수 꺼내기
        int k1 = q.top();
        q.pop();
        //두 번째 작은 수 꺼내기
        int k2 = q.top();
        q.pop();
        //공식대로 섞어서 q에 넣기
        q.push(k1 + (k2 * 2));
        //섞기를 진행했으니 카운트
        answer++;
    }
    
    return answer;
}

 

이처럼 가장 정렬 후 가장 큰 수, 가장 작은 수만 빠르게 꺼내야할 때 priority_queue를 사용하면 쉽고 효율적으로 문제를 해결할 수 있다.