1122. Relative Sort Array

본 알고리즘 풀이는 Routine Study에서 진행하고 있습니다.
저를 포함한 구성원이 대부분 초보이므로, 원하시는분은 언제라도 들어오셔도 좋습니다.

문의는 댓글 바람.

팀 알고리즘 레포지토리 주소

GitHub - ROUTINE-STUDY/Algorithm: 초보 알고리즘 스터디 / 누구나 참여 가능

문제 출처

Relative Sort Array - LeetCode

[처음 생각한 접근 방법]

1. arr1의 나오는 숫자들의 횟수를 세어준다.

2. arr2의 나오는 숫자들을 먼저 횟수만큼 배열에 넣어 준다.

3. 남은 나머지 숫자들을 배열에 넣어준다.

import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] answer = new int[arr1.length];
        Map<Integer, Integer> map = new HashMap<>();
        for (int num :  arr1){
            map.put(num, map.getOrDefault(map.get(num),0)+1);
        }

        int index = 0;
        for (int num : arr2) {
            int size = map.get(num);
            for (int i = 1; i <= size; i++) {
                answer[index++] = num;
                map.put(num, map.get(num)-1);
            }
        }

        List<Integer> list = new ArrayList<>();
        for (int num : arr1) {
            if (map.get(num) != 0) list.add(num);
        }
        Collections.sort(list);

        for (int num : list) {
            answer[index++] = num;
        }

        return answer;
    }
}

[리트코드 답안]

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        TreeMap<Integer, Integer> map = new TreeMap<>();
        for(int n : arr1) map.put(n, map.getOrDefault(n, 0) + 1);
        int i = 0;
        for(int n : arr2) {
            for(int j = 0; j < map.get(n); j++) {
                arr1[i++] = n;
            }
            map.remove(n);
        }
        for(int n : map.keySet()){
            for(int j = 0; j < map.get(n); j++) {
                arr1[i++] = n;
            }
        }
        return arr1;
    }
}

TreeMapd은 key를 정렬하여 넣는다는 것을 이용한 방법이다.

이렇게 순서를 정해두면 다시 정렬할 필요가 없어져서 아주 효율적이 된다.

[내 답안 수정하기]

import java.util.*;

class Solution {
    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        int[] answer = new int[arr1.length];
        Map<Integer, Integer> map = new TreeMap<>();
        for (int num :  arr1){
            map.put(num, map.getOrDefault(num,0)+1);
        }

        int index = 0;
        for (int num : arr2) {
            int size = map.get(num);
            for (int i = 1; i <= size; i++) {
                answer[index++] = num;
            }
            map.remove(num);
        }

        for (int num : map.keySet()) {
            for (int i = 0; i < map.get(num); i++) {
                answer[index++] = num;
            }
        }

        return answer;
    }
}

속도는 4ms로 더 느리긴한데 더 좋아보이긴 한다.

시간복잡도는 arr1 = n, arr2 = m, -> n+m이 아닐까 싶다.