[99클럽 코테 스터디 9일차 TIL] 정렬

문제

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

답

import java.util.Arrays;
import java.util.Collections;

class Solution {
    public String[] findRelativeRanks(int[] score) {
        Integer[] sortedScore = Arrays.stream(score).boxed().toArray(Integer[]::new);
        Arrays.sort(sortedScore, Collections.reverseOrder());

        Map<Integer, String> rankMap = new HashMap<>();
        for (int i = 0; i < sortedScore.length; i++) {
            if (i == 0) {
                rankMap.put(sortedScore[i], "Gold Medal");
            } else if (i == 1) {
                rankMap.put(sortedScore[i], "Silver Medal");
            } else if (i == 2) {
                rankMap.put(sortedScore[i], "Bronze Medal");
            } else {
                rankMap.put(sortedScore[i], String.valueOf(i + 1));
            }
        }

        String[] result = new String[score.length];
        for (int i = 0; i < score.length; i++) {
            result[i] = rankMap.get(score[i]);
        }

        return result;
    }
}

해결방안

일단 Arrays 의 sort를 이용해서 정렬을 한다. 그런데 내림차순으로 정렬을 하려면 Collections를 사용해서 정렬해야 해서 Interger타입으로 변환부터 했다.

그리고 정렬한 정렬과 원본 배열과 비교해서 순위를 저장해야 하는데 비교할때 List의 indexOf를 사용했다. 그런데 저번주 문제에서 indexOf는 시간복잡도 O(n) 를 가지고 있기 때문에, Map에 저장해서 찾는게 속도가 더 좋았던게 기억나서 HashMap을 사용해서 문제를 다시 풀었다.

회고

리트코드를 통해 코테를 풀어보긴 처음이였다. 매번 코테 문제 해석하는데 애 먹었는데, 오히려 영어가 더 이해하기 쉬웠다.
리트코드도 꾸준히 풀어봐야지. 아좌좌~