(C++) - 프로그래머스(고득점 kit - 힙(heap)) : 더 맵게 답

programmers.co.kr/learn/courses/30/lessons/42626

코딩테스트 연습 - 더 맵게

min heap으로 간단히 풀 수 있었던 문제였습니다.

 

 

풀이방법

 1. min heap인 priority_queue로 변수 pq를 선언합니다.

 2. scovile의 모든 원소를 삽입합니다. 이 때 min heap이므로 가장 작은 스코빌 원소가 tree level이 작은 곳에 위치합니다.

 3. pq의 원소가 2개이상이며 스코빌지수가 K보다 작은 동안에는 계속 음식을 섞습니다.

 4. 두 원소를 뽑고 공식을 이용해 섞은 이후 합쳐진 값을 다시 push해줍니다. 그 후 answer++

 5. 만약 다 섞은 후 top이 K이하면 만들 수 없으므로 -1를 반환합니다.

     아니라면 answer return;

Code

#include <bits/stdc++.h>
using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue <int, vector<int>, greater<int>> pq;
    for(int i = 0; i < scoville.size(); i++){
        pq.push(scoville[i]);
    }
    
    while(pq.size() >= 2 && pq.top() < K ){
        int scov1 = pq.top();
        pq.pop();
        int scov2 =  pq.top();
        pq.pop();
        pq.push(scov1 + scov2 * 2);
        answer++;
    }
    
    if(pq.top() < K) return -1;
    return answer;
}