[Hackerrank] Climbing the Leaderboard

문제 설명

아케이드 게임 플레이어가 리더보드에서 자신의 순위를 확인하고 기록하는 상황입니다.
리더보드는 Dense Ranking 방식을 사용합니다.

Dense Ranking 규칙:

• 점수가 높은 플레이어가 더 높은 순위를 가집니다.
• 동일한 점수를 가진 플레이어는 같은 순위를 가지며, 다음 순위는 건너뜁니다.

예시:
ranked = [100, 90, 90, 80, 75, 60]
player = [50, 65, 77, 90, 102]

리더보드 순위는 [1, 2, 2, 3, 4, 5]입니다.

플레이어의 점수별 순위는 다음과 같습니다:

• 50 → 6위
• 65 → 5위
• 77 → 4위
• 90 → 2위
• 102 → 1위

결과: [6, 5, 4, 2, 1]

---

입력 형식

1. n: 리더보드에 있는 점수의 개수
2. ranked: 리더보드 점수 리스트 (내림차순)
3. m: 플레이어가 게임을 한 횟수
4. player: 플레이어가 획득한 점수 리스트 (오름차순)

---

출력 형식

• 각 게임 후 플레이어의 순위를 리스트 형태로 반환합니다.

---

 

 

 

 

이 문제는 우선 ranked가 내림차순이고 player가 오름차순인 게 중요한 부분이라고 생각했다. 이는 앞에서부터 순위를 계산해도, 이전에 계산한 순위가 이후 순위 계산에 영향을 주지 않는다. 그리고 1 2 2 3 3 3 3 4 이런 방식으로 순위를 계산하니 (동일한 수는 동일한 등수로) 그러니 set로 바꾸어서 계산을 해주었다. 처음 고안해 본 코드는 다음과 같다.

def climbingLeaderboard(ranked, player):
    result = []
    ranked = list(set(ranked))
    for i in player:
        ans = 1
        for j in ranked:
            if j > i:
                ans += 1
            else:
                break
        result.append(ans)             
    return result

player에 있는 변수를 차례대로, ans를 늘려주면서 순위를 계산하는 방식을 이용했다. 이 방식을 이용하니 시간 초과에 걸려서 11개 중 3개를 통과하지 못했다. 그래서 시간을 많이 잡아먹는 부분이 for j in ranked 부분에서 하나씩 탐색하는 부분이라고 생각했다. (시간 복잡도가 O(m * n))그래서 이를 시간을 줄여주기 위해서 이진탐색 방법을 이용해서 코드를 다음과 같이 변경해 보았다.

def climbingLeaderboard(ranked, player):
    result = []
    ranked = list(set(ranked))
    for i in player:   
        start = 0
        end = len(ranked) - 1
        while start <= end:
            mid = (start + end) // 2
            if i < ranked[mid]:
                start = mid + 1
            else:
                end = mid - 1
        result.append(start + 1)             
    return result

이 방법은 위 방법과 동일하지만, 이진탐색을 이용해서 시간복잡도를 O(m log n)까지 줄인 방식이다. 위 방법으로 통과했다.

문제를 풀고 구글링을 하던 도중 위 방법(이진탐색이 아닌 실패했던 방법)의 시간을 더 줄일 방법을 찾았다.

def climbingLeaderboard(ranked, player):
    ranked = sorted(set(ranked), reverse=True)
    n = len(ranked)
    result = []
    index = n - 1  
    
    for score in player:
        while index >= 0 and score >= ranked[index]:
            index -= 1  
        result.append(index + 2)  
    return result

이 방법으로는 O(n + m)으로 시간을 줄일 수 있다.