[プログラマー]-失敗率(Python)

5024 ワード
アルゴリズム#アルゴリズム# テキストリンク

問題の説明


失敗率は次のように定義されます.
ステージに到着しても空になっていないプレイヤー数/ステージに到着したプレイヤー数
現在停止しているステージ番号を含む配列フェーズをパラメータとして指定した場合は、失敗率の高いステージからステージ番号を含む配列を降順に返すように、ソルバを完了します.

せいげんじょうけん

  • ステージの個数Nは1以上500以下の自然数である.
  • 段階の長さは1以上200000以下である.
  • 段階は、1以上N+1以下の自然数を含む.
  • 各自然数は、ユーザが現在挑戦しているステージの番号を示す.
  • 段、N+1は最後のステージ(Nステージ)にクリアしたユーザを表す.
  • 同じ失敗率の舞台があれば、まず小さいサイズの舞台がいいです.
    • プレイヤーが
  • ステージに到達しなかった場合、そのステージの失敗率は0と定義される.

    • I/O例


    Nstagesresult5[2, 1, 2, 6, 2, 4, 3, 3][3, 4, 2, 1, 5]4[4, 4, 4, 4, 4][4, 1, 2, 3]

    I/O例説明

  • I/O例#1

  • 1番ステージには8人のユーザーが挑戦し、そのうち1人のユーザーはまだ通関していない.そのため、1番ステージの失敗率は以下の通り.
    1ステージ失敗率:1/8

  • 第2ステージには7人のユーザーが挑戦し、そのうち3人のユーザーはまだ通関していない.そのため、2番目の舞台の失敗率は以下の通りです.
    フェーズ2失敗率:3/7

  • フェーズ3失敗率:2/4

  • フェーズ4失敗率:1/2

  • フェーズ5失敗率:0/1
    各ステージの番号を失敗率の降順に並べます.
    [3, 4, 2, 1, 5]
  • I/O例#2
  • はすべてのユーザが最後のステージにいるため、4番目のステージの失敗率は1であり、残りのステージの失敗率は0である.
    [4, 1, 2, 3] 
    • def solution(N, stages):
    answer = {}
    L = [0] * N               # 스테이지만큼 0 리스트 생성

    for i in range(1, N+1):
        for j in stages:
            if i == j:        # 각 사람마다 막힌 스테이지 
                L[i-1] += 1   # L리스트에 카운트

    A = len(stages)           # 사람수
    for k in range(N):
        if A != 0:
            answer[k+1] = (L[k] / A)   # answer 사전에 스테이지와 실패율 저장
            A -= L[k]
        else:                          # 사람수가 0이 될때까지
            answer[k+1] = 0
    # 실패율 내림차순으로 정렬  
    return sorted(answer, key = lambda x: answer[x], reverse = True)
    Java継承
    サバティカらないゲーム開発改めVJ製作ブログ3日目