[プログラマー/C++]もっと辛い
13137 ワード
https://programmers.co.kr/learn/courses/30/lessons/42626#
問題自体は簡単ですが、優先度を上げる方法が分からないので、構造体を使いました.探してみたが、他に方法がある...!
構造体
入力ベクトルのすべてのscoville値を
ドアの中
2つのトップを出して、新しい食べ物を作って押しました.
この場合、topのscoville値がKより大きいと、他のすべての食べ物が満たされるのでbreak;
またwhileゲートはpqです.size()>1にのみ移動!(新しい食べ物を作るには2つ必要です)
問題を解く
問題自体は簡単ですが、優先度を上げる方法が分からないので、構造体を使いました.探してみたが、他に方法がある...!
構造体
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; //내림차순
Reference
この問題について([プログラマー/C++]もっと辛い), 我々は、より多くの情報をここで見つけました https://velog.io/@inryu/프로그래머스-C-더-맵게テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol