LeetCode: Relative Ranks

You are given an integer array score of size n, where score[i] is the score of the ith athlete in a competition. All the scores are guaranteed to be unique.

The athletes are placed based on their scores, where the 1st place athlete has the highest score, the 2nd place athlete has the 2nd highest score, and so on. The placement of each athlete determines their rank:

• The 1st place athlete's rank is "Gold Medal".
• The 2nd place athlete's rank is "Silver Medal".
• The 3rd place athlete's rank is "Bronze Medal".
• For the 4th place to the nth place athlete, their rank is their placement number (i.e., the xth place athlete's rank is "x").

Return an array answer of size n where answer[i] is the rank of the ith athlete.

 

Example 1:

Input: score = [5,4,3,2,1]
Output: ["Gold Medal","Silver Medal","Bronze Medal","4","5"]
Explanation: The placements are [1st, 2nd, 3rd, 4th, 5th].

Example 2:

Input: score = [10,3,8,9,4]
Output: ["Gold Medal","5","Bronze Medal","Silver Medal","4"]
Explanation: The placements are [1st, 5th, 3rd, 2nd, 4th].

 

Constraints:

• n == score.length
• 1 <= n <= 10^4
• 0 <= score[i] <= 10^6
• All the values in score are unique.

 

이 문제는 우선순위 큐를 사용하여 푸는 문제이다. 

 

최대한 시간복잡도를 낮춰서 풀고 싶었기 때문에 다음과 같은 방식을 사용했다. 

 

1. 우선순위 큐를 사용한다. (라이브러리는 min heap기준이기 때문에 -1을 곱해서 사용하였다. )

2. 쌓은 heapq 값을 pop한 값을 딕셔너리에 저장한다.

    res[(-1) * heapq.heappop(heap)] = i +1 형태이다. (for i in range(len(score)): 안에 있기 때문에 등수를 i+1로 쓰기 가능)

    -1은 원본 값으로 되돌리기 위해 곱해주었다. 

3. 그리고 if 문들 for문에 같이 놓아서 1, 2, 3등은 메달로 바꿀 수 있도록 딕셔너리를 만들었다. 

    이렇게 만들어진 딕셔너리는 res[점수] = 등수 (메달있음 메달)  형태로 작성이 된다. 

 

4. 따라서 이후에는 score로 for문을 돌리면서 results.append(res[score])를 반복만 해주면 된다. 

    그러면 score와 같은 순서로 매핑된 등수가 results에 저장이 되는 방식이다.

 

이 방식은 이중 for문이 없어 시간복잡도가 O(nlogn)이다. 

 

 

 

---

구현 코드

 

class Solution(object):
    def findRelativeRanks(self, score):
        """
        :type score: List[int]
        :rtype: List[str]
        """

        res = {}
        results = []
        heap = []
        for sc in score:
            heapq.heappush(heap, -sc)

        for i in range(len(heap)):
            if i == 0:
                res[(-1)*heapq.heappop(heap)] = 'Gold Medal'
            elif i == 1:
                res[(-1)*heapq.heappop(heap)] = 'Silver Medal'
            elif i == 2:
                res[(-1)*heapq.heappop(heap)] = 'Bronze Medal'
            else:
                res[(-1)*heapq.heappop(heap)] = str(i+1)

        for i in range(len(score)):
            results.append(res[score[i]])


        return results