백준 18870. 좌표 압축 - java

문제 설명

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

import java.io.*;
import java.util.*;

public class Main {
    
    public static void main(String [] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        int n = Integer.parseInt(br.readLine());
        int [] arr = new int [n];
        Set <Integer> set = new TreeSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i = 0; i< n ; i++){
            int num =Integer.parseInt(st.nextToken());
            arr[i]= num;
            set.add(num);
        }

        Map <Integer , Integer> map = new HashMap<>();
        int idx = 0;
        for(int i : set){
            map.put(i,idx++);
        }

        for(int i = 0; i< n; i++){
            sb.append(map.get(arr[i])).append(" ");
        }
        System.out.println(sb);
    }
    
}

 

1. 좌표 압축이란?

좌표압축(Coordinate Compression) 은 

좌표값의 범위를 줄여서 더작은 값으로 변환하는 기법. 

주로 좌표의 상대적인 순서를 유지하면서도 

원래 크기보다 작은 값으로 표현할 때 사용한다.

 

2. 왜 사용하는가? 

1) 메모리 절약

좌표값이 매우 클 경우 그대로 저장하면 

메모리를 많이 차지

2) 시간 복잡도 개선

좌표를 작은 범위의 값으로 변환하면 

배열 인덱싱을 활용 할 수 있어

탐색 및 정렬 속도가 향상됨 . 

 

3. 구현 순서

좌표 정렬 후 중복제거(같은 값이면 순서가 같음) 

해당 좌표의 새로운 값 찾기(원래 좌표가 어디에 위치하는지 찾기) 

 

구현 순서

1. 원래 배열 arr 을 생성(원본의 위치정보를 위해) 

2. 정렬, 중복제거 위해 TreeSet 사용 

3. map 에 새롭게 정의한 좌표 넣기 (Key 값은 원본 값) 

4. map에서 key값을 원본값으로 주면서 출력