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

이것은.. 가장 작은 것에 대해서만 조사한다는 힌트가 주어졌다는 것을 알아채고

Heap을 구성한다면 풀 수 있는 문제다.

https://programmers.co.kr/learn/courses/30/lessons/42626?language=cpp 

 

---

 

#맞는 풀이

#include <string>
#include <vector>
#include <queue>
#include <functional> // 비교함수 greater나 less가 들어있음

//Min Heap을 구성하여 가장 맵지 않은 음식이 맨 위로 오게하자.


using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<int, vector<int>, greater<int>> pq; // 크면 밑으로가는 Min Heap을 말함 less가 comparator가 되면 Max Heap임
    //모조리 집어넣음
    for(int x : scoville){
        pq.push(x);
    }
    
    //1. 가장 맵지않은 것을 꺼냄 -> 현재 가장 안매움
    //1-2 가장 맵지 않은 것이 K 이상이면 종료
    //2. 남은 것중에 가장 맵지 않은 것을 꺼냄 -> 현재 두번째로 안매움
    //3. 섞어서 다시 넣음 (count)
    
    //유의사항: 2개를 꺼낼 수 있느냐 check
    
    //K보다 작으면 계속 진행함
    while(pq.top() < K){
        if(pq.size() >= 2){
            int x1 = pq.top();
            pq.pop();
            int x2 = pq.top();
            pq.pop();
            int res = x1 + x2*2;
            pq.push(res);
            answer++;
        }else{
            //한개 뿐인데다 K보다 작으면 시도할 수 없음
            return -1;
        }
    }
    
    return answer;
}

 

Heap을 구성할 떄

prioirty_queue를 쓰게 되는데

 

<queue>에 들어있고

<functional>에 Comparator가 들어있으니 잘 쓰면 되겠다.