오랜만에 알고리즘 포스팅이다.

일단 문제부터 보자

문제

문제만 보면 매우 간단하다...(lv.0 문제)

처음 문제를 봤을 때 우선순위큐..? 라고 생각을 했는데 0레벨 문제에서 그럴 일은 없을 것 같고...

Stream이랑 람다식을 떡칠하면 되게 간단할 것 같긴 한데...
함수식을 다 외우지를 못해서 그건 불가능하다고 판단해서 논리의 흐름대로 해결해보려고 한다.

문제 풀이

1. Map 만들기

일단 나는 Map을 사용해서 풀어볼 예정이다.
반복문의 중첩을 좋아하지 않기 때문에 비약적으로 탐색 속도를 해결하고자 한다.

class Solution {
    public int[] solution(int[] emergency) {
        // 맵을 하나 만들기
        HashMap<Integer, Integer> newMap = new HashMap<>();
        int x = 0;
        for (int i : emergency) {
            newMap.put(i,x);
            x++;
        }
    }
}

위의 코드와 같이 맵을 만들어 탐색 속도를 높일 수 있도록 했다.
(다만 간단한 코드라 영향은 없을 것 같긴한데...)

2. 내림차순 정렬

맵을 만들었다면 내림차순 정렬을 할 수 있도록 추가적인 리스트를 만들도록 하겠다.

class Solution {
    public int[] solution(int[] emergency) {
        
        // 정렬이 될 배열 하나 더 만들기
        List<Integer> newList = new ArrayList<Integer>() {{for (int i : emergency) add(i);}};
        // 내림차순 정렬
        Collections.sort(newList, Collections.reverseOrder());
        
    }
}

일단 단순히 배열을 복사하는게 아니라 새로 ArrayList로 선언 후 배열을 복사한 이유는
원본 배열의 보존을 위해서이다.

문제에서 보면 원본 배열의 원소 순서가 유지되어 있는것이 보이는데 이 부분을 해결하고자 ArrayList를 사용했다.

또한 기존의 배열보다 ArrayList가 유연하게 데이터를 사용할 수 있기 때문에 사용했다.

3. Map의 Value 변경

이제 정렬된 List와 Map이 존재했으니 Value의 순서대로 Map의 값을 바꿀 수 있게 되었다.

import java.util.*;

class Solution {
    public int[] solution(int[] emergency) {
       
        // 맵의 값을 변경한다.
        int y = 1;
        for (int i : newList) {
            if (newMap.containsKey(i)) {
                newMap.replace(i, y);
            }
            y++;
        }
       
    }
}

정렬된 리스트에서 나오는 요소와 같은값이 Key가 존재 한다면
해당 Key의 값이 y의 값으로 변경하도록 하며 순회를 하면 할수록 값이 증가된다

먼저 나오는 순서일수록 우선 순위가 높다는 뜻

맵의 값을 변경하기 전에 값이 이렇게 나온다면

맵의 값을 변경한다면 이렇게 바뀌는 것을 볼 수 있다.

4. 원본 배열의 값을 변경

이제 바뀐 맵의 값을 통해 원본 배열을 순회하면서 값을 변경하면 된다.

class Solution {
    public int[] solution(int[] emergency) {
        
        for(int i = 0; i < emergency.length ; i++) {
            int value = newMap.get(emergency[i]);
            emergency[i] = value;
        }
        
    }
}

전체 코드

import java.util.*;

class Solution {
    public int[] solution(int[] emergency) {
        // 맵을 하나 만들기
        HashMap<Integer, Integer> newMap = new HashMap<>();
        int x = 0;
        for (int i : emergency) {
            newMap.put(i,x);
            x++;
        }
        // 정렬이 될 배열 하나 더 만들기
        List<Integer> newList = new ArrayList<Integer>() {{for (int i : emergency) add(i);}};
        
        // 내림차순 정렬
        Collections.sort(newList, Collections.reverseOrder());
        
        // 맵의 값을 변경한다.
        int y = 1;
        for (int i : newList) {
            if (newMap.containsKey(i)) {
                newMap.replace(i, y);
            }
            y++;
        }
        
        for(int i = 0; i < emergency.length ; i++) {
            int value = newMap.get(emergency[i]);
            emergency[i] = value;
        }
        
        return emergency;
    }
}

시간 복잡도

해당 코드의 시간 복잡도는 O(N log N)이다.
정렬을 제외한 반복문의 시간복잡도는 O(N)에 수렴하지만 정렬 알고리즘은 O(N log N)이며
최악의 경우가 시간복잡도가 되기 때문이다.