[2024] day 130. Leetcode 506. Relative Ranks

2024년부터 새롭게 다시 시작하는 코딩테스트

2024년 5월 8일 (수)
Leetcode daily problem

506. Relative Ranks

https://leetcode.com/problems/relative-ranks/?envType=daily-question&envId=2024-05-08

Problem

크기 n의 정수 배열 점수가 제공된다. 여기서 점수[i]는 대회에서 i번째 선수의 점수이다. 모든 점수는 고유하다.

선수들은 자신의 점수에 따라 순위가 매겨지고, 1위 선수는 가장 높은 점수를 받고, 2위 선수는 두 번째로 높은 점수를 받는 식으로 배정된다. 각 선수의 배치에 따라 순위가 결정된다.

1위 선수의 순위는 'Gold Medal'이다.
2위 선수의 순위는 'Silver Medal'이다.
3위 선수의 순위는 'Bronze Modal'이다.

4위부터 n위까지의 선수의 순위는 배치 번호이다(즉, x위 선수의 순위는 "x"입니다).
답변[i]가 i번째 선수의 순위인 경우 n 크기의 답변 배열을 반환한다.

Solution

sort

상대적인 순위를 찾는 문제를 해결하기 위해 주어진 점수 리스트를 내림차순으로 정렬하고, 각 점수에 대해 순위를 부여한다.
상위 3명의 경우에는 지정되어 있는 네이밍이 있기 때문에 하드 코딩했고,나머지 순위들은 숫자 형태의 순위를 부여한다.

Code

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        sorted_score= sorted(score, reverse=True)
        rank_score = {}
        for i in range(len(sorted_score)):
            if i == 0:
                rank_score[sorted_score[i]] = 'Gold Medal'
            elif i == 1:
                rank_score[sorted_score[i]] = 'Silver Medal'
            elif i == 2:
                rank_score[sorted_score[i]] = 'Bronze Medal'
            else:
                rank_score[sorted_score[i]] = str(i+1)
        
        return [rank_score[s] for s in score]

Complexicity

시간 복잡도

주어진 score 배열을 sort 하면서 O(n log n)이 소요되었고,
score를 탐색하는데 O(n)이 소요된다.
총 시간 복잡도는 O(n log n)이다.

공간 복잡도

내림차순으로 정렬된 score를 저장하는 추가적인 공간과 각 점수에 대한 순위를 저장하는 공간으로 score 리스트의 길이인 n 만큼 사용하고 있어 총 공간 복잡도는 O(n)이다.