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

https://programmers.co.kr/learn/courses/30/lessons/42626#

문제 풀이

문제 자체는 엄청 쉬운데 우선순위큐를 오름차순 하는 법을 잘 몰라서 구조체를 사용했다. 찾아보니 다른 방법도 있다...!

구조체 priority_queue를 만들고, 이때 구조체는 scoville 기준 min heap이 되도록 하였다.
입력 벡터에 있는 모든 scoville값을 priority_queue에 push하여 자동 정렬되도록 하고

while문 안에서
top 두 개를 하나씩 꺼내고, 새로운 음식을 만들어서 push했다.
이때, top의 scoville값이 K보다 크면 다른 모든 음식도 모두 만족하기에 break;
또한 while문은 pq.size()>1 일 때까지만 돈다! (2개가 있어야 새 음식을 만들 수 있음)

코드

#include <string>
#include <vector>
#include <queue>
#include <iostream>
using namespace std;

struct Food{
    int scoville;
    Food(int a){scoville=a;}
    bool operator<(const Food &b)const{
        return scoville>b.scoville; //작은 게 top에!
    }
};

int solution(vector<int> scoville, int K) {
    int answer = 0;
    priority_queue<Food> pq;
    for(auto sc:scoville){pq.push(Food(sc));}
    
    bool flag=0;
    while(pq.size()>1){
        int food1=pq.top().scoville; pq.pop();
        int food2=pq.top().scoville; pq.pop();
        
        pq.push(Food(food1+2*food2));
        answer++;
        
        if(pq.top().scoville>=K) {flag=1; break;}  
    }
    
    if(!flag) answer=-1;
    
    return answer;
}

프로그래머스 다른 풀이

#include <vector>
#include <queue>

using namespace std;

int solution(vector<int> scoville, int K) {
    int answer = 0;
    int needHot;
    priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());

    while(pq.top()<K) {
        if(pq.size()==1) return answer = -1;
        needHot=pq.top(); pq.pop();
        pq.push(needHot+pq.top()*2);
        pq.pop(); answer++;
    }

    return answer;
}

priority_queue<int,vector<int>,greater<int>> pq (scoville.begin(),scoville.end());

priority_queue 두 번째, 세 번째 인자를 지정해줌으로써 오름차순 정렬이 되도록 하고 선언과 동시에 바로 scoville 벡터를 넣어준 모습!

👽 우선순위 큐의 오름차순 내림차순

  priority_queue<int, vector<int>, greater<int>> pq1; //오름차순
  priority_queue<int, vector<int>, less<int>> pq2; //내림차순