[백준] 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을 공백 한 칸으로 구분해서 출력한다.

---

풀이

좌표 압축이란 탐색해야 할 좌표가 많을 경우 불필요한 좌표들을 지우는 방식을 말한다.

예를 들어 탐색 알고리즘을 사용할 때 데이터의 양이 많을 경우 불필요한 좌표들을 지우고 정점의 좌표들만 남기는 좌표 압축 방식을 사용한다.

이 문제는 주어진 좌표들의 각 순위를 출력하는 문제이다.

방장의 풀이방식은 아래와 같다.

1. 좌표의 개수를 입력받는다.

2. 좌표 개수 크기의 배열을 2개 생성한다.

3. 두 배열에 좌표값을 입력받은 후 한 배열을 오름차순으로 정렬한다.

4. 해쉬맵을 생성하고 int 변수를 0으로 생성한다.

5. 오름차순으로 정렬된 배열에 값이 해쉬맵에 키로 존재하지 않을 경우

key를 배열의 값, value를 int변수로 담고 int변수를 1만큼 증가시킨다.

6. 정렬되지 않은 배열을 반복시켜 각 원소의 값을 map의 key로 조회해서 value값을 출력시킨다.

 

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

public class Main {
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        // [1]
        int n = Integer.parseInt(br.readLine());
        st = new StringTokenizer(br.readLine());
	// [2]
        int[] arr = new int[n];
        int[] arr2 = new int[n];
	// [3]
        for (int i = 0; i < n; i++) {
            arr[i] = arr2[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(arr2);
        // [4]
        Map<Integer, Integer> map = new HashMap<>();
        int rank = 0;
        // [5]
        for(int i = 0; i < n; i++) {
            if(!map.containsKey(arr2[i])) {
                map.put(arr2[i], rank);
                rank++;
            }
        }
        // [6]
        StringBuilder sb = new StringBuilder();
        for(int i = 0; i < n; i++) {
            sb.append(map.get(arr[i]) + " ");
        }
        System.out.println(sb);
    }
}