506. Relative Ranks (해석 + 풀이)

조건:

• n == score.length
• 1 <= n <= 104
• 0 <= score[i] <= 106
• All the values in score are unique.

의역: 각 고유한 값을 가진 정수형 배열이 들어올 때 해당 배열의 인덱스에 맞추어서 1등이면 Gold Medal 2등이면 Silver Medal 3등이면 Bronze Medal 그 외라면 각 순위를 문자열로 담은 문자열 배열을 반환하라.

 

풀이:

1. 단순 반복

class Solution {
    // 시간 복잡도 O(n^2) 공간 복잡도 O(n)
    public String[] findRelativeRanks(int[] score) {
        String price[] = {"Gold Medal","Silver Medal","Bronze Medal"};
        int indexHighArray[] = new int[score.length];
        String ans[] = new String[score.length];

        for (int i=0;i<score.length;i++){
            int tmp = -1; int index=0;
            for(int j=0;j< score.length;j++){
                if(tmp<score[j]){
                    tmp = score[j];
                    index = j;
                }
            }
            score[index] = -1;
            indexHighArray[i] = index;
        }
        // 만들어 진 것 크기가 큰 수 부터 내림 차순의 인덱스 배열
        for(int i=0;i<score.length;i++){
            if(i<3)
                ans[indexHighArray[i]]=price[i];
            else
                ans[indexHighArray[i]]=(i+1)+"";
        }
        return ans;
    }
}

예상외로 모든 풀이 중 가장 사용 메모리가 적었다.

 

2. TreeSet, Map 자료구조 활용

import java.util.HashMap;
import java.util.Iterator;
import java.util.TreeSet;

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String[] findRelativeRanks1(int[] score) {
        String price[] = {"mask","Gold Medal","Silver Medal","Bronze Medal"};
        String ans[] = new String[score.length];
        HashMap<Integer,Integer> map = new HashMap<Integer,Integer>();
        TreeSet<Integer> tset = new TreeSet<Integer>();
        // TreeSet을 활용하여 자동 정렬
        for (int num:score)
            tset.add(num);

        Iterator<Integer> it = tset.iterator();
        // map에 key를 배열의 값 value를 배열에서의 값의 순위 정보 저장
        int order = score.length;
        while(it.hasNext()){
            int key = it.next();
            map.put(key,order--);
        }
        // Map에 저장된 순위 정보를 불러와 ans 배열 생성
        for(int i=0;i<score.length;i++){
            int value = map.get(score[i]);
            if(value<=3)
                ans[i]=price[value];
            else
                ans[i]=(value)+"";
        }
        return ans;
    }
}

확실히 시간 복잡도를 O(n^2)을 O(n)으로 줄이니 속도가 개선된 모습 

+ 아래 함수들을 TreeMap 대신 사용하면 더 빠르게 개선이 가능

int[] copy = score.clone();
Arrays.sort(copy);

 

3. 기수 정렬 이용 Map을 긴 배열로 대체 

class Solution {
    // 시간 복잡도 O(n) 공간 복잡도 O(n)
    public String[] findRelativeRanks2(int[] score){
        int peapleNum = score.length;
        String[] ans = new String[peapleNum];
        int max = 0;
        for (int num: score)
            max = max<=num? num:max;
        int scoreArray[] = new int[max+1];

        // 가장 큰 수+1 만큼의 길이의 배열을 만들고 각 해당하는 수의 인덱스에 순위정보 저장
        for(int i=0;i<score.length;i++)
            scoreArray[score[i]] = i+1;

        int rank = 1;
        for(int i=scoreArray.length-1;i>=0;i--){
            if(rank> peapleNum) break;
            // scoreArray 배열에서 score 배열에 있는 수 만을 활용 하게끔 하는 조건
            // 자바에서 정수형 배열은 생성 후 따로 값을 초기화 하지 않으면 자동으로 0
            if(scoreArray[i]>0){
                switch (rank){
                    case 1:ans[scoreArray[i] - 1] = "Gold Medal";rank++; break;
                    case 2:ans[scoreArray[i] - 1] = "Silver Medal";rank++; break;
                    case 3:ans[scoreArray[i] - 1] = "Bronze Medal";rank++; break;
                    default: ans[scoreArray[i]-1] = rank+""; rank++; break;
                }
            }
        }
        return ans;
    }
}

메모: 가급적 만들 수 있는 자료구조를 사용하지 않고 해결이 가능하다면 사용하지 말고 풀이 해볼 것