RelativeRanks_LeetCode

 

<문제>

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

 

 

<풀이>

import heapq

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
            result = [None] * len(score)
            heap = [-n for n in score]
            heapq.heapify(heap)

            for i in range(1, len(score)+1):
                biggest = -heapq.heappop(heap)
                idx = score.index(biggest)

                if i == 1:
                    result[idx] = 'Gold Medal'
                elif i == 2:
                    result[idx] = 'Silver Medal'
                elif i == 3:
                    result[idx] = 'Bronze Medal'
                else:
                    result[idx] = str(i)
            
            return result

 

- 큰 숫자 순서대로 뽑는 것을 생각해서 heap 사용

- 리스트 변환 O(N), heapify O(N)

- heappop(heap) O(log N), index 찾는 부분 O(N) -> 반복문까지 O(N * (N + log N)) = O(N2)

- 전체 시간복잡도는 O(N2)

 

이번엔 해시테이블로 접근

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        sorted_score = sorted(score, reverse=True)
        rank_map = {val:i for i, val in enumerate(sorted_score)}
        ans = []

        for val in score:
            rank = self.convert_rank(rank_map[val])
            ans.append(rank)
        return ans
    
    def convert_rank(self, idx):
        if idx == 0:
            return "Gold Medal"
        elif idx == 1:
            return "Silver Medal"
        elif idx == 2:
            return "Bronze Medal"
        else:
            return str(idx + 1)

 

- sorted 내장함수 시간복잡도는 O(N log N)

- 해시테이블 만드는데 O(N)

- 전체 시간복잡도는 O(N log N)

- 훨씬 간단하면서 빠른 코드가 되었다

- 최소/최대값이라고 무작정 힙을 쓰지 말고 더 효율적인 방법이 있는지 생각해보자