[アルゴリズム/java]プリンタ

問題の説明

一般的なプリンタでは、必要な印刷順に印刷されます.したがって、重要なドキュメントは後で印刷される可能性があります.この問題を解決するために,重要文書を先に印刷するプリンタを開発した.この新しく開発されたプリンタは、次のように印刷されます.
印刷待ちリスト

から、先頭の文書(J)を取り出す.

残りの

個の印刷対象リストにJよりも重要なドキュメントがある場合は、Jを印刷対象リストの最後に配置します.

でなければJを印刷します.
例えば、4つの文書(A、B、C、D)が印刷対象リストに順次存在し、重要度が2 1 3 2の場合、CD A Bの順に印刷される.

私が印刷を要求したドキュメントが何回目の印刷なのか知りたいです.上記の例では、Cは1位、Aは3位である.
ソリューション関数を作成してください.パラメータが現在のキュー・リスト内のドキュメントの重要度のソート順と、印刷を要求したドキュメントが現在のキュー・リスト内にある場所を指定した場合、印刷を要求したドキュメントの何回目の印刷かを返します.

せいげんじょうけん

現在のキュー・リストには、100個未満の1つ以上のドキュメントが含まれています.
印刷ジョブの重要性は1～9で表され、数字が大きいほど重要です.
locationには0未満の値(現在のキューリストのタスク数-1)があり、キューリストの一番前にある場合は0、2番目にある場合は1と表示されます.

I/O例

priorities [2, 1, 3, 2]
location 2
return 1
priorities [1, 1, 9, 1, 1, 1]
location 0
return 5

I/O例説明

例1
問題の例は次のとおりです.
例2
6つの文書(A、B、C、D、E、F)は、印刷対象リストにおいて、重要度が1 1 1 1 9 1 1 1 1であり、C D E F A Bの順に印刷される.

アクセス

は、最初にPriority classを作成し、優先度とインデックス値を加えて格納しようとした.

の一番前から比較して、自分より大きい数が並んでいる場合は、一番後ろにキューを引いて、一番前まで最大の数を繰り返します.

でもこれは想像以上に...コードが冗長になりました.

だから全て削除して考えたのですが、優先順位Qを書くのが最適な方法です.

最初の試み

public class Prio{
    int index;
    int pri;

    public Prio(int index, int pri){
        this.index = index;
        this.pri = pri;        
    }
}

と書いてありましたが….最後に削除しました.

Code

import java.util.*;

class Solution {
    public int solution(int[] priorities, int location) {
        int answer = 0;
        
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder()); //큰 수 부터 우선 순위 부여.
        
        for(int priority: priorities){
            pq.offer(priority); //큐에 넣어주고
        }
        
        while(!pq.isEmpty()){
            for(int i=0; i<priorities.length; i++){
                if(pq.peek()==priorities[i]){
                    pq.poll(); //기존 배열과 요소가 일치하다면 뺀다. 
                    answer++;
                    if(location == i){ //기존 배열과 요소가 일치하는데 인덱스도 일치한다면 종료시킨다.
                        pq.clear();
                        break;
                    }
                }
            }
        }        
        return answer;
    }
}

📌 KeyNote

問題が多すぎます.

優先順位Qを考えると、すぐに解決できる問題.

PriorityQueue pq = new PirorityQueue<>(Collections.reverseOrder);