99클럽 코테 스터디 파이썬 비기너 17일차 Relative Ranks

문제

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

From LeetCode, https://leetcode.com/problems/relative-ranks/

답안

import heapq

class Solution:
    def findRelativeRanks(self, score: List[int]) -> List[str]:
        result = []

        # Sort scores with a heap
        heaped_score = [-s for s in score] ## Need a maximum heap
        heapq.heapify(heaped_score)
        heaped_score = sorted(heaped_score)

        # Match with sorted scores
        for s in score:
            idx = heaped_score.index(-s)

            # Append the result
            if idx == 0:
                result.append("Gold Medal")
            elif idx == 1:
                result.append("Silver Medal")
            elif idx == 2:
                result.append("Bronze Medal")
            else:
                result.append(str(abs(idx) + 1))

        return result

원리

1. 입력받은 점수 배열을 복사한다. 이때, 최대 힙을 사용하기 위해 모든 값을 음수로 변환하여 받는다.
2. 복사한 배열을 힙으로 만든 후 형제 노드의 순서도 적절하도록 한 번 더 정렬을 한다.
3. 모든 점수에 대해 3번을 반복한다. 힙에서 자신의 위치를 찾아 해당하는 결과 값을 결과 배열에 저장한다.

구현

• arr.index(element)는 배열에서 찾는 값의 인덱스를 반환한다. 이때, 배열에 찾는 값이 없다면 TypeError가 발생하기 때문에, 보장되지 않은 경우 조건문으로 예외 처리를 해야 한다.

후기

LeetCode는 처음 써 보는데 굉장히 마음에 든다! '답을 클래스의 메소드로 작성하게 하는 이유가 뭐지?' 했는데 디버깅을 위해 출력을 해 보고 깨달았다. 표준 출력과 반환값을 구분해 주어서 훨씬 편하다! 또, 시간 복잡도도 분석이 되고 런타임이랑 메모리 사용률도 랭킹으로 보여준다! 마음에 든다. 흥미롭다. (비록 오늘도 런타임 상위 92%로 처참한 효율을 뽐냈지만.) 추천받은 적 있는 LeetCode 100제 같은 걸 활용해서 공부해 보아야지.

🎇 최적화

1. 힙은 형제 노드끼리 순서가 안 맞을 수 있어서 힙-화 후에 정렬을 한 건데, 생각해 보면 '이 문제에서 굳이 힙을?' 같긴 하다. 정렬만 하면 되잖아..?
2. 인덱스 함수는 O(N)이다. 그래서 N회의 반복문 안에 들어가는 바람에 전체 실행 시간이 O(N^2)이 되었다. 해시 매핑 (딕셔너리) 사용을 통해 O(1)로 인덱스를 찾고, 전체 실행 시간을 O(N)으로 만들 수 있었다.