(c++)프로그래머스 코딩테스트 연습 - 더 맵게

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

코딩테스트 연습 - 더 맵게

[풀이]

queue라이브러리의 우선순위 큐로 힙을 구현하였다.

 

Min Heap : 부모노드가 자식노드보다 작음

priority_queue<int,vector<int>,greater<int>>q

 

Max Heap : 부모노드가 자식노드보다 큼

priority_queue<int>q

priority_queue<int,vector<int>,less<int>>q

 

이 문제에서는 가장 맵지 않은 음식 두개를 가지고 섞어야 하므로 top에 제일 작은 수가 오는 Min Heap을 사용해야한다.

 

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

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    //min_heap
    priority_queue<int,vector<int>,greater<int>>q;
    for(int i=0;i<scoville.size();i++){
        q.push(scoville[i]);
    }
    while(q.top()<K){
        //모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우
        if(q.size()<2){
            answer=-1;
            break;
        }
        int s1=q.top();
        q.pop();
        int s2=q.top();
        q.pop();
        int s3=s1+(s2*2);
        q.push(s3);
        answer++;
    }
    return answer;
}