[プログラマー]失敗率

23299 ワード

プログラマ亥時テキストリンク

def solution(N, stages):
    answer = []
    FRbyStage = dict()
    denom = len(stages)

    for i in range(1, N+1):
        moleclue = stages.count(i)
        #if no one reached i-stage
        if denom == 0: FRbyStage[i] = 0
        else:
            FRbyStage[i] = moleclue/denom
            denom -= moleclue

    #sort by dict(hash)_value
    FRbyStage = sorted(FRbyStage.items(), key=lambda value: value[1], reverse=True)
    for key,value in FRbyStage: answer.append(key)
    return answer

私のコードを説明

1. Input

def solution(N, stages):

ステージ全体の数N;ゲームを使用するユーザが現在停止しているステージの番号を含むレイアウトステージ.

2. Process

FRbyStage = dict()

Stageをキーとし、そのStageの失敗率を値とするdictionary(hash-table)FRByStage変数を宣言します.

denom = len(stages)

初期denom値はstages配列の長さとして宣言されます

for i in range(1, N+1):
    moleclue = stages.count(i)
    #if no one reached i-stage
    if denom == 0: FRbyStage[i] = 0
    else:
    	FRbyStage[i] = moleclue/denom
        denom -= moleclue

手順1～N+1を繰り返します.(ステージ総数)
ムーア手がかりがこの段階で停止した人数
denomはこの段階を通過した人数を表す
FRByStage dictは、このフェーズの失敗率を格納します.

#if no one reached i-stage
if denom == 0: FRbyStage[i] = 0

この段階を通過する人がいなければ、すなわち0に分けた場合に例外処理が与えられる.

#sort by dict(hash)_value
FRbyStage = sorted(FRbyStage.items(), 
key=lambda value: value[1], reverse=True)

dictデータ型を基準に並べ替えます.

for key,value in FRbyStage: answer.append(key)
return answer

ソート関数を使用してdict型をtuple型に変換します.したがって,上記のように,キー値のみを回答リストに追加して返す.

3. Output

失敗率の高いステージから、ステージ番号を含む配列を降順に返します.

テストコード実行時間

私のコードテスト例の実行時間

테스트 1 〉	통과 (0.01ms, 10.1MB)
테스트 2 〉	통과 (0.14ms, 10.2MB)
테스트 3 〉	통과 (64.64ms, 10.4MB)
테스트 4 〉	통과 (325.67ms, 10.8MB)
테스트 5 〉	통과 (1402.24ms, 14.8MB)
테스트 6 〉	통과 (1.17ms, 10.1MB)
테스트 7 〉	통과 (13.61ms, 10MB)
테스트 8 〉	통과 (324.58ms, 10.8MB)
테스트 9 〉	통과 (1304.15ms, 14.9MB)
테스트 10 〉	통과 (131.05ms, 10.8MB)
테스트 11 〉	통과 (340.38ms, 10.8MB)
테스트 12 〉	통과 (201.02ms, 11.3MB)
테스트 13 〉	통과 (426.82ms, 11.4MB)
테스트 14 〉	통과 (0.04ms, 10.2MB)
테스트 15 〉	통과 (10.49ms, 10.7MB)
테스트 16 〉	통과 (5.34ms, 10.3MB)
테스트 17 〉	통과 (11.40ms, 10.5MB)
테스트 18 〉	통과 (5.75ms, 10.2MB)
테스트 19 〉	통과 (1.14ms, 10MB)
테스트 20 〉	통과 (8.93ms, 10.3MB)
테스트 21 〉	통과 (17.14ms, 10.7MB)
테스트 22 〉	통과 (1080.11ms, 18.2MB)
테스트 23 〉	통과 (19.11ms, 11.7MB)
테스트 24 〉	통과 (72.51ms, 11.5MB)

[プログラマ]他の人のコードプールへのリンク

def solution(N, stages):
    answer = []
    fail = []
    info = [0] * (N + 2)
    for stage in stages:
        info[stage] += 1
    for i in range(N):
        be = sum(info[(i + 1):])
        yet = info[i + 1]
        if be == 0:
            fail.append((str(i + 1), 0))
        else:
            fail.append((str(i + 1), yet / be))
    for item in sorted(fail, key=lambda x: x[1], reverse=True):
        answer.append(int(item[0]))
    return answer

他者コードテストケース実行時間

테스트 1 〉	통과 (0.03ms, 10.3MB)
테스트 2 〉	통과 (0.08ms, 10.3MB)
테스트 3 〉	통과 (1.86ms, 10.5MB)
테스트 4 〉	통과 (6.22ms, 10.9MB)
테스트 5 〉	통과 (12.22ms, 15MB)
테스트 6 〉	통과 (0.20ms, 10.3MB)
테스트 7 〉	통과 (0.66ms, 10.4MB)
테스트 8 〉	통과 (5.78ms, 10.8MB)
테스트 9 〉	통과 (12.05ms, 15MB)
테스트 10 〉	통과 (5.92ms, 10.9MB)
테스트 11 〉	통과 (6.20ms, 11MB)
테스트 12 〉	통과 (9.51ms, 11.4MB)
테스트 13 〉	통과 (9.88ms, 11.3MB)
테스트 14 〉	통과 (0.04ms, 10.3MB)
테스트 15 〉	통과 (4.20ms, 10.5MB)
테스트 16 〉	통과 (2.03ms, 10.4MB)
테스트 17 〉	통과 (3.99ms, 10.5MB)
테스트 18 〉	통과 (2.18ms, 10.4MB)
테스트 19 〉	통과 (0.44ms, 10.4MB)
테스트 20 〉	통과 (2.88ms, 10.4MB)
테스트 21 〉	통과 (6.65ms, 10.8MB)
테스트 22 〉	통과 (13.00ms, 18MB)
테스트 23 〉	통과 (14.31ms, 11.6MB)
테스트 24 〉	통과 (12.27ms, 11.6MB)
테스트 25 〉	통과 (0.02ms, 10.3MB)
테스트 26 〉	통과 (0.04ms, 10.3MB)
테스트 27 〉	통과 (0.02ms, 10.4MB)

私のコードのテスト例の実行時間は全体的に遅いです.
原因を見つけてから修正する.

原因の特定

1.countの時間的複雑さ

for i in range(1, N+1):
	moleclue = stages.count(i) 
    	#count 연산은 시간복잡도 O(n)

他の人よりコードが遅い主な要因はcountです.
count演算はリスト全体を検索するので,時間複雑度をO(n)と計算し,周囲のfor文の時間複雑度を加えるとO(n^2)となる.

info = [0]*(N+2)
for stage in stages: info[stage] +=1
for i in range(1, N+1):
	moleclue = info[i]

したがってcount演算ではなくinfoという配列が作成される.

2.無駄な価値を探る

FRbyStage = sorted(FRbyStage.items(), key=lambda value: value[1], reverse=True)
#해당 for문에서 value 값은 사용되지 않는다.
for key,value in FRbyStage: answer.append(key)
return answer

重複文ではvalueは使用されないので意味がありません.修正したコードは以下の通りです.

for item in sorted(FRbyStage.items(), key=lambda value: value[1], reverse=True): answer.append(item[0])
return answer

最終コード

修正された完全なコード

def solution(N, stages):
    answer = []
    FRbyStage = dict()
    denom = len(stages)
    info = [0]*(N+2)

    for stage in stages: info[stage] +=1

    for i in range(1, N+1):
        moleclue = info[i]
        #if no one reached i-stage
        if denom == 0: FRbyStage[i] = 0
        else:
            FRbyStage[i] = moleclue/denom
            denom -= moleclue
   
    #sort by dict(hash)_value
    for item in sorted(FRbyStage.items(), key=lambda value: value[1], reverse=True): 
    	answer.append(item[0])
    return answer

修正されたコードの実行時間は次のとおりです.

테스트 1 〉	통과 (0.01ms, 10.3MB)
테스트 2 〉	통과 (0.06ms, 10.2MB)
테스트 3 〉	통과 (0.73ms, 10.5MB)
테스트 4 〉	통과 (5.45ms, 10.9MB)
테스트 5 〉	통과 (11.87ms, 14.9MB)
테스트 6 〉	통과 (0.18ms, 10.2MB)
테스트 7 〉	통과 (0.58ms, 10.2MB)
테스트 8 〉	통과 (5.51ms, 11MB)
테스트 9 〉	통과 (16.41ms, 14.9MB)
테스트 10 〉	통과 (6.00ms, 10.9MB)
테스트 11 〉	통과 (5.81ms, 10.9MB)
테스트 12 〉	통과 (9.11ms, 11.4MB)
테스트 13 〉	통과 (9.71ms, 11.4MB)
테스트 14 〉	통과 (0.02ms, 10.2MB)
테스트 15 〉	통과 (6.42ms, 10.6MB)
테스트 16 〉	통과 (1.94ms, 10.3MB)
테스트 17 〉	통과 (4.10ms, 10.7MB)
테스트 18 〉	통과 (3.64ms, 10.3MB)
테스트 19 〉	통과 (0.71ms, 10.3MB)
테스트 20 〉	통과 (3.94ms, 10.5MB)
테스트 21 〉	통과 (5.65ms, 10.9MB)
테스트 22 〉	통과 (12.10ms, 18.4MB)
테스트 23 〉	통과 (12.16ms, 11.7MB)
테스트 24 〉	통과 (11.60ms, 11.7MB)
테스트 25 〉	통과 (0.01ms, 10.2MB)
테스트 26 〉	통과 (0.01ms, 10.2MB)
테스트 27 〉	통과 (0.01ms, 10.2MB)

文章はこれで終わります.ありがとうございます.😊

Reference

この問題について([プログラマー]失敗率), 我々は、より多くの情報をここで見つけました https://velog.io/@hisg123/프로그래머스-실패율

テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。

Collection and Share based on the CC Protocol

Spring Batchメタデータ

210813開発ログ