506. Relative Ranks

Description

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

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

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

Return an array answer of size n where answer[i] is the rank of the i^th 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⁴
• 0 <= score[i] <= 10⁶
• All the values in score are unique.

Submitted Code

import heapq

class Solution(object):
    def findRelativeRanks(self, score):
        """
        :type score: List[int]
        :rtype: List[str]
        """
        max_heap = []   # 최대힙
        place = 1       # 현재 등수 저장

        for idx, s in enumerate(score):
            heapq.heappush(max_heap, (-s, idx))   # 요소의 값(음수변환)과 인덱스 함께 저장

        while max_heap:
            idx = heapq.heappop(max_heap)[1]      # 가장 큰 수가 추출됨(인덱스 값만 가져오기)

            if place == 1:
                score[idx] = "Gold Medal"
            elif place == 2:
                score[idx] = "Silver Medal"
            elif place == 3:
                score[idx] = "Bronze Medal"
            else:
                score[idx] = str(place)
    
            place += 1    # 다음 등수로 이동
    
        return score

Runtime: 15 ms | Beats 39.31%
Memory: 13.40 MB | Beats 38.32%

파이썬 내장 모듈인 heapq로 리스트를 최소힙처럼 다룰 수 있다. 최대힙으로 만들기 위해서는 score 값에 -를 붙여서 추가하는 트릭이 필요하다.

Other Solutions

1st

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        sorted_score = sorted(score, reverse=True)
        medals = ["Gold Medal", "Silver Medal", "Bronze Medal"]
        rank_mapping = {score: medals[i] if i < 3 else str(i + 1) for i, score in enumerate(sorted_score)}
        return [rank_mapping[score] for score in score]

time complexity: 𝑂(𝑛log𝑛)
space complexity: 𝑂(𝑛)

sorted() 함수로 점수를 정렬한 후, 점수와 순위를 매핑하는 방법이다.

score = [10, 3, 8, 9, 4]

sorted_score = [10, 9, 8, 4, 3]
rank_mapping = {
                 10: "Gold Medal",
                  9: "Silver Medal",
                  8: "Bronze Medal",
                  4: "4",
                  3: "5"
               }

return [“Gold Medal”, “5”, “Bronze Medal”, “Silver Medal”, “4”]