[プログラマー]失敗率


🐶 問題の説明



これはゲームの各ステージの失敗率を計算することで、ステージ上の番号を降順に並べて返す問題です!
ステージに到着しても空になっていないプレイヤー数/ステージに到着したプレイヤー数
現在停止しているステージ番号を含む配列フェーズをパラメータとして指定した場合は、失敗率の高いステージからステージ番号を含む配列を降順に返すように、ソルバを完了します.
-->失敗率の詳細の表示

🐷 せいげんじょうけん


舞台の個数Nは1以上500以下の自然数である.
ステージの長さは1以上200000以下です.
ステージは、1以上N+1以下の自然数を含む.
各自然数は、ユーザが現在挑戦しているステージの番号を表します.
ただし、N+1は、最後のステージ(N番目のステージ)にクリアしたユーザを表す.
同じ失敗率の舞台があれば、トランペットの舞台を先に来てもらうことができます.
ステージに到着したプレイヤーがいない場合、そのステージの失敗率は0と定義されます.

🐨 Javaプール

import java.util.*;
class Solution {
    public int[] solution(int N, int[] stages) {
    	// 1. 
        int[] curStatus = new int[N];
        // 2. 
        Map<Integer,Double> result = new HashMap<>();
        // 3. 
        for(int user:stages){
            if(N >= user){
                 curStatus[user-1] += 1; 
            }
        }
        // 4.
        int failer;
        for(int i=0; i<N; i++){
            // 5.
            failer =0;
            for (int j=0;j<i;j++){
                failer += curStatus[j];
            }
            // 6.
            Double val = Double.valueOf(curStatus[i])/(stages.length-failer);
            // 7.
            if(Double.isInfinite(val)||Double.isNaN(val)){
                val = 0.0;
            }
            // 8.
            result.put(i+1,val);
        }
        // 9. 
        List<Integer> keySet = new ArrayList<>(result.keySet());
        // 10.
        Collections.sort(keySet, (o1,o2)->(result.get(o2).compareTo(result.get(o1))));
      	// 11.
        return keySet.stream().mapToInt(i->i).toArray();
    }
}

🌈 説明する


  • ステージごとにプレイヤー数を格納できる配列curstateを生成した.

  • そして最後に結果値を保存した結果をMapで生成する.

  • 各プレイヤーの現在位置を含むステージ配列をforゲートにし、各ステージのプレイヤー数をcurtStateに入れる.
    全ステージ数Nが5の場合、stages=[2,1,2,6,2,4,3]であり、curstateは[1,3,2,1,0]を含む.countが6番目のステージプレイヤーの数を含まないのは,Nが5であれば6はすべてのステージを完了したことを意味するため,ゲームは失敗しなかったからである.

  • int型のfailerを宣言し、現在のステージより前のステージのプレイヤー数を含み、ステージの総数でドアを開ける.

  • failerを0に初期化すると、前のステージの数をドアに変換して、現在のステージの前のステージにあるプレイヤーの数を取得し、failerに蓄積することができます.

  • そして、스테이지에 도달했으나 아직 클리어하지 못한 플레이어의 수 / 스테이지에 도달한 플레이어 수を救うために、現在のステージのプレイヤー数curStatus[i]の中からステージに到達したプレイヤー数stages.length-failerを分ける.この場合、数値プレースホルダを比較するためにdouble型valに値を格納します.

  • ステージに到達したプレイヤー数が0の場合、Doubleを分割すると無限大またはNaNになるので、DoubleのメソッドisInfinite()とisNaN()を使用してこの値をチェックすることができます.いずれかがtrueの場合、valは0に設定されます.

  • HashMapのresultではkeyroがステージポジションを表し,valueが獲得したばかりのvalを表す.

  • resultのキーのみがkeysetとしてリストに入れられています

  • Collectionsのsortメソッドを使用してkeySetをソートし、compareTo()メソッドを使用して次の値を現在の値より大きく設定すると、前に進みます.

  • 最後に,Listをint型の配列に設定する.
  • -->ダウンジャケットで失敗率を確認

    🔥 性能検査


    せいど
    試験1〉合格(3.91 ms,52.7 MB)
    テスト2〉合格(4.16 ms,53.3 MB)
    試験3〉合格(28.17 ms,54.3 MB)
    試験4〉合格(16.95 ms,56.3 MB)
    試験5〉合格(22.16 ms,63.1 MB)
    試験6〉合格(5.84 ms,52.8 MB)
    テスト7〉合格(5.43 ms,53.7 MB)
    試験8〉合格(9.48 ms,56.3 MB)
    試験9〉合格(14.35 ms,61.8 MB)
    試験10〉合格(11.24 ms,55.5 MB)
    試験11〉合格(10.1 ms,56.5 MB)
    テスト12〉合格(16.42 ms,57.1 MB)
    テスト13〉合格(10.23 ms,60.1 MB)
    テスト14〉合格(9.17 ms,52.5 MB)
    試験15〉合格(5.90 ms,54.7 MB)
    テスト16〉合格(4.84 ms,54.4 MB)
    テスト17〉合格(7.56 ms,55.1 MB)
    テスト18〉合格(4.23 ms,53.4 MB)
    試験19〉合格(3.32 ms,53.3 MB)
    試験20〉合格(8.86 ms,54.7 MB)
    テスト21〉合格(8.72 ms,55.8 MB)
    テスト22〉合格(11.11 ms,65 MB)
    試験23〉合格(10.20 ms,60.2 MB)
    テスト24〉合格(12.68 ms,59.2 MB)
    試験25〉合格(8.41 ms,52.8 MB)
    テスト26〉合格(7.16 ms,52.5 MB)
    試験27〉合格(6.38 ms,52.4 MB)

    🐰 草を切る

    def solution(N, stages):
        answer = {}
        user = []
        
        for i in range(1,N+1):
            user.append(stages.count(i))
            d = (len(stages) - sum(user[:i-1]))
            answer[i] = float(stages.count(i))/ d if d else 0
    
        return sorted(answer,key=lambda x:answer[x] ,reverse=True)
    -->ダウンジャケットで失敗率を確認

    🌈 説明する


    ジャワに似ていますが、もっと短くできます.stages.count(i)により、ステージごとのプレイヤー数を蓄積することなく一度に保存することができる.
    またjavaでは、failerには前のステージにいるプレイヤーの数が含まれており、sumが1つで重複する必要はありません.内部でfor文のような動作をしたかもしれませんが、論理的にはより直感的で、より簡単です.
    doubleの場合、isInfinite()メソッドとisNaN()メソッドを使用して例外処理(?)を行います.以下のように簡単になりました.answer[i] = float(stages.count(i))/ d if d else 0最後に,解答リストを降順にソートするためにソート関数に対してreverse=Trueを行い,lambda式を用いて解答中のxのキー値に基づいて比較するように設定した.
    今日もアルゴリズムがPythonと呼ばれて終わった.

    🔥 性能検査


    せいど
    試験1〉合格(0.03 ms,10.2 MB)
    試験2〉合格(0.41 ms,10.4 MB)
    テスト3〉合格(127.63 ms,10.4 MB)
    試験4〉合格(638.57 ms,10.9 MB)
    試験5〉合格(2782.91 ms,14.8 MB)
    試験6〉合格(2.84 ms,10.2 MB)
    試験7〉合格(43.55 ms,10.2 MB)
    試験8〉合格(692.22 ms,10.9 MB)
    試験9〉合格(2566.87 ms,15 MB)
    試験10〉合格(275.34 ms,10.8 MB)
    テスト11〉合格(702.35 ms,10.8 MB)
    テスト12〉合格(373.06 ms,11.3 MB)
    試験13〉合格(792.69 ms,11.3 MB)
    試験14〉合格(0.09 ms,10.2 MB)
    試験15〉合格(22.34 ms,10.5 MB)
    試験16〉合格(10.76 ms,10.3 MB)
    試験17〉合格(50.50 ms,10.5 MB)
    テスト18〉合格(12.33 ms,10.4 MB)
    テスト19〉合格(2.38 ms,10.3 MB)
    試験20〉合格(42.50 ms,10.4 MB)
    テスト21〉(31.26 ms,10.9 MB)
    試験22〉合格(228.64 ms,18.3 MB)
    テスト23〉合格(21.89 ms,11.7 MB)
    テスト24〉合格(106.36 ms,11.7 MB)
    試験25〉合格(0.01 ms,10.1 MB)
    試験26〉合格(0.03 ms,10.2 MB)
    試験27〉合格(0.01 ms,10.2 MB)
    しかし私は何かを间违えたようです...テスト5、9、22などから見ると、Javaにははるかに及ばない.彼はどうしたの.

    🐸 の最後の部分


    このノートはまだ他に残したい人の解答を発見していない.
    また、JavaでのテストケースとPythonでのテストケースの違い、または同じ理由を知りたいのですが、私の論理は間違っていて、Pythonでの速度測定がもっと遅いです.
    時間の複雑さについては、遅かれ早かれよく勉強しなければならないと思います.
    明らかにsumやcountのような方法が内部でfor文のように機能するのは、そのためだと思います.
    短くて直感的な論理が良いのか、長くて性能の良い論理が良いのか.
    これから勉強することが多すぎます~~
    [ソース:プログラマ]