[백준] 18870번: 좌표 압축 - JAVA

🔗 문제 링크

BOJ 18870번: 좌표 압축

18870번: 좌표 압축

 

📝 풀이 과정

예시를 통해 문제를 먼저 이해했다.

// 입력
2 4 -10 4 -9

// 출력
2 3 0 3 1

문제를 보면 현재 좌표보다 작은 좌표들의 개수가 압축값이 되고, 좌표 값이 같은 여러 개의 좌표가 있어도 1개로 취급하는 것을 알 수 있다.

 

 

int[] sortNums = nums.clone();
Arrays.sort(sortNums);

Arrays.sort는 기존의 배열을 정렬시켜 기존 배열을 알 수 없으므로 미리 nums.clone()을 통해 배열을 깊은 복사한 뒤 오름차순으로 정렬하였다.

 

 

int idx = 0;
for (int n : sortNums)
    if (!map.containsKey(n))
        map.put(n, idx++);

다음으로 Map을 활용하여 <좌표값, 좌표값의 최소 인덱스>를 저장하기로 하였다. 정렬된 sortNums를 반복문을 돌며, 만약 map에 이미 존재하는 좌표라면 무시하고 아니라면 map.put을 사용하여 좌표값과 인덱스를 저장하고 인덱스를 하나 증가시켜 주었다.

 

이후 기존 배열의 좌표값으로 map.get을 통해 인덱스 값을 얻어오면 된다.

 

⏱ 시간 복잡도

Arrays.sort의 경우 dual pivot quicksort을 사용하여 $O(n\log n)$
반복문에서 Map의 get과 set, containsKey 메소드는 O(1)이기 때문에 $O(n)$

 

따라서 전체 함수의 시간복잡도는 $O(n\log n)$이다.

 

💻 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        String[] input = br.readLine().split(" ");
        int[] nums = new int[N];
        for (int i = 0; i < N; i++)
            nums[i] = Integer.parseInt(input[i]);

        int[] sortNums = nums.clone();
        Arrays.sort(sortNums);

        Map<Integer, Integer> map = new HashMap<>();
        int idx = 0;
        for (int n : sortNums)
            if (!map.containsKey(n))
                map.put(n, idx++);

        StringBuilder sb = new StringBuilder();
        for (int n : nums)
            sb.append(map.get(n)).append(' ');

        System.out.println(sb.toString());


    }
}

 

📊 제출 결과