[HackerRank] Climbing the Leaderboard
https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem
に答える
に答える
ref: https://inspirit941.tistory.com/199
python listのsortで解決しようとしたところ、timelimitに遭遇した.bsで検索しても同じです.
def climbingLeaderboard(ranked, player):
# Write your code here
result = []
from collections import defaultdict
rank_dict = defaultdict(int)
for r in ranked:
rank_dict[r] += 1
for p in player:
score = list(rank_dict.keys())
score.append(p)
score.sort(reverse=True)
for idx, s in enumerate(score):
if s == p:
break
result.append(idx + 1)
return result
timelimitを解決するために、pを探すたびに検索しようとすることはできません.コアはplayerが降順であり、ランキングが昇順である点を利用し、検索する必要のない領域を利用することです.def climbingLeaderboard(ranked, player):
queue = sorted(set(ranked), reverse=True)
idx = len(queue) - 1
result = []
for p in player:
while queue[idx] <= p and idx >= 0:
idx -= 1
if idx < 0:
result.append(1)
continue
result.append(idx + 2)
return result
plyaerとranderのソート順のため、playerの前にある値はranderの後ろに表示されます.そこで,プレイヤを反復する場合,順位の後ろからチェックを行う.また、キューが多すぎるindexでは、再検索する必要はありません.
この方法では,順位の長さにかかわらず,順位を1回巡回すればよい.
負数索引
idxが負数の場合があります.このことは、ランキング内のすべての要素をソートするときに発生します.したがって、pは1位になるので、結果に1を追加します.
コード#コード#
https://github.com/naem1023/codingTest/blob/master/implementation/hackerrank-climbing-the-leaderboard.py
Reference
この問題について([HackerRank] Climbing the Leaderboard), 我々は、より多くの情報をここで見つけました
https://velog.io/@naem1023/HackerRank-Climbing-the-Leaderboard
テキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol
def climbingLeaderboard(ranked, player):
# Write your code here
result = []
from collections import defaultdict
rank_dict = defaultdict(int)
for r in ranked:
rank_dict[r] += 1
for p in player:
score = list(rank_dict.keys())
score.append(p)
score.sort(reverse=True)
for idx, s in enumerate(score):
if s == p:
break
result.append(idx + 1)
return result
def climbingLeaderboard(ranked, player):
queue = sorted(set(ranked), reverse=True)
idx = len(queue) - 1
result = []
for p in player:
while queue[idx] <= p and idx >= 0:
idx -= 1
if idx < 0:
result.append(1)
continue
result.append(idx + 2)
return result
https://github.com/naem1023/codingTest/blob/master/implementation/hackerrank-climbing-the-leaderboard.py
Reference
この問題について([HackerRank] Climbing the Leaderboard), 我々は、より多くの情報をここで見つけました https://velog.io/@naem1023/HackerRank-Climbing-the-Leaderboardテキストは自由に共有またはコピーできます。ただし、このドキュメントのURLは参考URLとして残しておいてください。
Collection and Share based on the CC Protocol