99클럽 코테 스터디 9일차 TIL (Relative Ranks) - LeetCode

오늘 문제는 Leetcode라는 사이트에서 풀게된 첫 문제이다.

---

1. 오늘의 학습 키워드

• 정렬

---

2. 문제: 506. Relative Ranks

• 단계: Easy
• 주제: Array, Sorting, Heap (Priority Queue)
• 출처: https://leetcode.com/problems/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 <= 104
• 0 <= score[i] <= 106
• All the values in score are unique.

---

3. 나의 풀이

접근 방법

leetcode 문제는 처음 푼다. 먼저 문제를 천천히 적어가며 이해해보자.

1. 사이즈 n 의 리스트 score가 있다.
2. score[i]에는 i번째의 운동선수의 점수가 들어있다.
   • score[3]은 세번째로 참가한 운동선수의 점수라고 보면 된다.
3. 1등은 "Gold Medal" , 2등은 "Silver Medal", 3등은 "Bronze Medal" 을 받고, 4등부터 n등은 2번에서 말한 그 위치에 해당하는 값의 리스트를 리턴해라
   • ex) ans[4] = 4등, ans[n] = n등

이제 예시를 살펴보자.

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].

score[0]은 5점으로 가장 높다. 따라서 output 리스트의 첫번째 요소는"Gold Medal" , score[1]은 4점으로 두 번째로 높다. 따라서 두번째 요소는 "Silver Medal" , 나머지 요소들도 동일하게 적용한다면 결과는 ["Gold Medal","Silver Medal","Bronze Medal","4","5"].

두 번째 예시를 살펴보자.

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].

score[0]은 10점으로 가장 높다. 따라서 output 리스트의 첫번째 요소는 "Gold Medal" , score[1]은 가장 작으므로 가장 작은 값인 “5”, score[2]은 "Bronze Medal" , score[3]은 "Silver Medal" , score[4]는 4등으로 “4”이다.

최종적인 결과는 ["Gold Medal","5","Bronze Medal","Silver Medal","4"]가 나온다.

이 문제를 접근하기 위해선 우선 score리스트를 내림차순으로 먼저 만든다.

그런다음 딕셔너리 변수를 만들고, 키에는 점수, 값에는 그 점수의 등수를 표기한다.

마지막으로, 이 점수가 1, 2, 3등이면 "Gold Medal" , "Silver Medal" , "Bronze Medal" 을 주고 나머지는 인덱스 값을 주면 된다.

실제로 구현해보며 위 내용이 어떻게 구현되고 변경될 지를 확인해보자.

1. score 리스트를 내림차순으로 변경한다. 왜냐하면 나중에 딕셔너리 변수에 점수와 점수의 등수를 입력해야하는데, 내림차순으로 변경된 score을 반복문으로 돌리면서 값을 넣어야 하기 때문에!!

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

        """
        sorted_score = sorted(score,reverse=True) # 1. score 리스트를 내림차순으로 변경

2. 점수와 등수를 기록할 딕셔너리 변수 설정 및 값 채우기

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

        """
        sorted_score = sorted(score,reverse=True)

        rank = {}
        ans = []

        for i in range(len(sorted_score)):
            rank[sorted_score[i]] = i

두 번째 예시를 적용해보면 다음과 같다.

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

rank = {10:0, 9:1, 8:2, 4:3, 3:4}

3. score의 크기만큼 반복문을 돌면서 rank의 값이 0이면 "Gold Medal" , 1이면 "Silver Medal" , 2이면 "Bronze Medal" 을 지정하고, 3부터는 (index+1)값을 준다. 왜냐하면 index는 0부터 시작하기 때문! , 또한 결과 리스트에 숫자는 str형태로 나타나므로, str(index+1)로 진행한다.

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

        """
        sorted_score = sorted(score,reverse=True)

        rank = {}
        ans = []

        for i in range(len(sorted_score)):
            rank[sorted_score[i]] = i

        for i in range(len(score)):
            if rank[score[i]] == 0:
                ans.append('Gold Medal')
            elif rank[score[i]] == 1:
                ans.append('Silver Medal')
            elif rank[score[i]] == 2:
                ans.append('Bronze Medal')
            else:
                ans.append(str(rank[score[i]]+1))

        return ans

마지막 반복문이 score 리스트에 대해서 도는 이유는 간단하다.

output 리스트 (ans)는 score리스트의 각 요소들이 몇등인지를 나타내는 값이기 때문이다.

---

4. 결과

TestCase

Result

https://leetcode.com/problems/relative-ranks/submissions/1346297517

Time Complexity

Let n be the length of score.

• Time complexity: O(nlogn) We traverse the score array once and populate scoreToIndex. Since inserting in a hashmap takes O(1) time on average, the entire operation takes O(n). Collisions are unlikely since the scores are guaranteed to be unique according to the constraints. —> 내 코드에서 rank 딕셔너리 Sorting the the score array array takes O(nlogn). → sorted_score 리스트 정렬 Finally, traversing the score array and assigning ranks to athletes takes O(n). → 마지막 반복문 The dominating term is O(nlogn).
  

---

5. 결론

지금까지 프로그래머스, 백준에만 집중했었는데 LeetCode도 괜찮은 것 같은데??

읽어주셔서 감사합니다.