[Hackerrank]Climbing the Leaderboard

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

Climbing the Leaderboard | HackerRank

 

후기

• 문제 입력 조건을 꼼꼼히 봐야함.
• scores의 경우 내림차순으로(100, 90, 80, ...) 입력받고, alice의 경우 오름차순(50, 60, 79, ...)으로 입력받는다.
• 처음에는 입력 조건 제대로 안보고 scores list를 매번 반복문을 통해 순회하며 올바른 등수를 찾았지만, 시간초과 남.
• 나중에 입력 조건 확인 후, 정렬된 값으로 입력받기 때문에 alice 등수를 한쪽 방향으로만 증가 혹은 감소하도록 구현 -> scores를 한 번 순회하면 등수를 구할 수 있음 -> O(n) 시간복잡도로 계산할 수 있음.

파이썬 코드

def climbingLeaderboard(scores, alice):
    # scores를 오름차순으로 정렬
    scores = sorted(list(set(scores)))
    index = 0
    result = []    
    length = len(scores)
    for a in alice:
        # alice의 점수가 score[index]보다 작을 때까지 index 증가시킴.
        while index < length and a >= scores[index]:
            index += 1
        result.append( length+1 - index)
    return result