[プログラマー/レベル2]プリンタ(C++)

[プログラマー/レベル2]プリンタ(C++)

1.質問

2.アクセス/チェックポイント

同じ優先度の文書が複数ある可能性があるため、同じ優先度の文書が検索する文書のインデックス(場所)と同じであることを確認する必要があります.確認するには、

の優先度とインデックスを組み合わせる必要があります->pair().

3.解決方法

優先順位queue(優先順位キュー)を使用して、すべてのドキュメントを優先順位降順にソートします.
->この場合、ソート順は優先度基準(インデックスを考慮しない場合)の出力順です.

優先度のインデックスとそのインデックスの優先度のペア()がキューに格納されます.

優先キューが空であるか、検索するドキュメント(場所)が見つかるまで出力を繰り返します.

の優先度に合致する場合(出力可能である場合)、キューから削除され、count(出力順序を検証するための変数)の数が増加します.

の優先順位に合致しない場合は、キューの最後の1つに再び追加されます.

4.完全なコード

#include <vector>
#include <queue>
#include<utility>  //pair() 사용
using namespace std;

int solution(vector<int> priorities, int location) {
    int answer = 0;
    int count = 0;
    
    queue<pair<int,int>> q;  //priorities의 순서(idx)와 우선순위를 쌍으로 저장할 큐
    
    priority_queue<int> pq; //우선순위에 따라 내림차순으로 저장할 우선순위 큐
    
    //pq에 우선순위 저장(내림차순), 큐에 idx와 우선순위 순서쌍 저장
    for(int i=0; i<priorities.size(); i++){
        pq.push(priorities[i]);
        q.push(make_pair(i,priorities[i]));
    }
    
    while(!pq.empty()){  //대기 목록이 없을 때 까지 반복
        
        int idx = q.front().first;
        int val = q.front().second;
    
        //우선순위와 대기 순서가 일치한다면 => 출력
        if(val == pq.top()){
            
            pq.pop();
            q.pop();
            count++;  //출력 순서 count용
            
            if(idx == location){  //해당 문서가 내가 궁금한 인쇄물이라면
                answer = count;  //몇 번째 순서로 출력되는지 확인
                break;
            }
        }else{  //우선순위가 더 높은 문서가 있다면 맨 뒤로 보내기
            q.pop();
            q.push(make_pair(idx,val));
            
        }
        
    }

    
    return answer;
}

5.注意事項

👉 C++優先キュー-優先キュー

1.queueuヘッダファイルを含む

#include> queue

2.優先キュー宣言

priority_queue<int> pq; 
priority_queue<int, vector<int>, less<int>> pq;

は、いずれも大きい値から並べ替えられる降順優先キュー

である.

3.優先キューに要素を挿入

pq.push(2) 

の通常のキューに要素を挿入する方法と同様の方法

4.まず、ガードキューの要素を取り出します。

pq.top() 

優先キューの最上位要素(優先度の高い要素)

を取り出す.

5.優先順位キュー昇順の設定

priority_queue<int, vector<int>, greater<int>> pq;

と宣言された場合、優先キューは昇順に並べられ、最小値から出力されます.

または基本的な方法で要素をプッシュする場合は、負の値に変更することもできます.

6.他の方法を試みる

後で追加します

7.後期

後で追加します