[HackerRank] Climbing the Leaderboard

https://www.hackerrank.com/challenges/climbing-the-leaderboard/problem

Soluzione

ref: https://inspirit941.tistory.com/199 Provando a risolvere con il sort delle liste Python si superava il time limit. Neanche la binary search aiutava.

1
def climbingLeaderboard(ranked, player):
2
    # Write your code here
3
    result = []
4
    from collections import defaultdict
5
    rank_dict = defaultdict(int)
6
    for r in ranked:
7
        rank_dict[r] += 1
8

9
    for p in player:
10
        score = list(rank_dict.keys())
11
        score.append(p)
12
        score.sort(reverse=True)
13
        for idx, s in enumerate(score):
14
            if s == p:
15
                break
16
        result.append(idx + 1)
17

18
    return result

Per risolvere il time limit, non si può cercare da zero per ogni p. L’intuizione chiave è che player è in ordine crescente e ranked in ordine decrescente, quindi si possono saltare le regioni che non necessitano di ricerca.

1
def climbingLeaderboard(ranked, player):
2
    queue = sorted(set(ranked), reverse=True)
3

4
    idx = len(queue) - 1
5
    result = []
6

7
    for p in player:
8
        while queue[idx] <= p and idx >= 0:
9
            idx -= 1
10
        if idx < 0:
11
            result.append(1)
12
            continue
13
        result.append(idx + 2)
14
    return result

Per via degli ordinamenti di player e ranked, i valori più bassi in player corrispondono alle posizioni più arretrate in ranked. Quindi iterando su player, controlliamo ranked dalla fine. Una volta superato un indice nella coda, non serve rivisitarlo. In questo modo, indipendentemente dalla dimensione di ranked, lo si attraversa una sola volta.

Indice negativo

idx può diventare negativo. Succede quando tutti gli elementi di ranked sono stati attraversati. In quel caso, p è al 1° posto, quindi aggiungiamo 1 al risultato.

Codice

https://github.com/naem1023/codingTest/blob/master/implementation/hackerrank-climbing-the-leaderboard.py