[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