[프로그래머스] C++ 더 맵게

[프로그래머스] 고득점Kit 힙 - 더 맵게

 

< 문제 > 

 

< 풀이 >

#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>> pq_scoville;
    
    for(int i =0; i< scoville.size(); i++)
    {
        pq_scoville.push(scoville[i]);
    }
    
    while(true)
    {        
        int first_scoville = pq_scoville.top();
        pq_scoville.pop();
        int second_scoville = pq_scoville.top();
        pq_scoville.pop();
        
        if(K <= first_scoville)
            break;
        else if(first_scoville < K)
        {    
            pq_scoville.push(first_scoville + second_scoville*2);
            answer++;
        }
        
        if(pq_scoville.size() == 1)
            break;
    }
    
    if(pq_scoville.size() == 1 && pq_scoville.top() < K )
            return -1;
    
    return answer;
}

 

< 해설 >

힙의 첫번째 문제!

우선순위 큐 (priority_queue)를 이용해서 구현했다. 우선순위큐는 오름차순으로 설정해준 뒤 사용했다. 

priority_queue<int, vector<int>, greater<int>>  가 아닌 priority_queue<int, vector<int>>  를 사용하면 가장 큰 수부터 정렬이 되는점을 조심하자. (근데 사실 우선순위 큐가 완벽하게 정렬이 되는것은 또 아니다.. 근데 문제를 풀 때는 이 부분은 과감히 생략했음. 하지만 꼭 알고는 있어야 한다.)

 

우선순위 큐에 데이터들을 다 넣고 난 뒤에 top의 데이터 2개를 꺼내서 first_scoville, second_scoville 을 설정해준다. 여기서 first_scoville의 값이 스코빌 지수 K보다 크다면 바로 while문을 빠져나온다. 그렇지 않다면 음식 두개를 섞어서 다시 우선순위 큐에 넣어주면된다. 그리고 while문 마지막에 우선순위 큐의 사이즈가 1이라면(더이상 2가지를 섞을 수 없기 때문에) while문을 빠져나오도록 한다.

 

return -1는 전부다 계산을 했음에도 스코빌 지수가 K를 넘지 않는다면 음식의 스코빌 지수가 K이상으로 만들 수 없다고 판단하여 -1을 해주게된다.