[プログラマー/C++]もっと辛い


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

問題を解く


問題自体は簡単ですが、優先度を上げる方法が分からないので、構造体を使いました.探してみたが、他に方法がある...!
構造体priority_queue、このとき構造体はscoville基準minheapである.
入力ベクトルのすべてのscoville値をpriority_queueに押して自動的にソートします.
ドアの中
2つのトップを出して、新しい食べ物を作って押しました.
この場合、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は、2番目、3番目の因子を昇順に並べて指定し、宣言と同時にscovilleベクトルを直ちに加える様子!

👽 優先順位キューの昇順と降順

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