[Java] BOJ 18870 좌표 압축

문제 

문제 링크 https://www.acmicpc.net/problem/18870

• 수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.
• X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.
• Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.
• 첫째 줄에 N이 주어진다.
• 둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.
• 첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

아이디어

• 좌표값을 저장할 때 배열에 한번 저장하고 TreeSet에 한번 더 저장한다.
• TreeSet에 저장하는 이유는 중복값을 제거하고 정렬하기 위해서이다.
• 그리고 HashMap에 TreeSet에 저장한 값을 Key로, 순서를 저장할 변수를 선언하고 1씩 카운트하여 Value값으로 저장한다. (오름차순으로 정렬되었기 때문에 순서대로 카운트한 값이 순서가 된다.)
• 그리고 처음에 저장한 배열값으로 HashMap에서 검색하여 순서를 결과값 배열에 저장한다.

겪은 시행착오

• X

좀 더 쉽게 풀 수 있는 방법이 있을 것 같은데 나중에 공부해봐야겠다...!

코드

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

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

        // 좌표 개수
        int N = Integer.parseInt(br.readLine());

        // 좌표값을 넣을 배열
        int arr[] = new int[N];

        // 좌표값을 정렬할 treeset(중복값을 제외하기 위해)
        TreeSet<Integer> arr2 = new TreeSet<>();

        // 좌표값과 압축 좌표값을 저장할 Hashmap
        HashMap<Integer, Integer> graph = new HashMap<>();

        // 결과값을 저장할 배열
        int result[] = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());

        // 배열에 좌표값을 저장
        for(int i = 0; i < N; i++){
            int x = Integer.parseInt(st.nextToken());

            arr[i] = x;
            arr2.add(x);
        }

        // 순서
        int cnt = 0;

        // 정렬한 treeset의 값을 key로, 순서를 value로 hashmap에 저장
        for(int i : arr2){
            graph.put(i, cnt);

            // 순서 + 1
            cnt = cnt + 1;
        }

        for(int i = 0; i < arr.length; i++){
            // 결과값에 배열의 값을 이용하여 hashmap에 저장되어있는 value값을 저장
            result[i] = graph.get(arr[i]);
        }

        for(int i = 0; i < result.length; i++){
            sb.append(result[i] + " ");
        }

        System.out.println(sb);
    }
}