[Java] 18870번. 좌표 압축 (# TreeMap)

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

keypoint)
문제 설명이 난해하지만
결국 2번째 줄로 주어지는 숫자들을 낮은 순으로 랭크를 0, 1, 2, ... 로 매기는 것이다.
가령 첫번째 예제 입력1의 경우에
"2 4 -10 4 -9" 가 주어지는데
2는 3번째로 작은수이므로 2로
4는 4번째로 작은수이므로 3으로
-10은 1번째로 작은수이므로 0으로
4는 4번째로 작은수이므로 3으로
-9는 3번째로 작은수이므로 1로 바꾸어서
"2 3 0 3 1"로 출력하면 된다.
생각보다 단순해보일수도 있는데 생각없이 코드를 짜면 시간초과가 당신을 기다린다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;
import java.util.TreeMap;

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());
        
        //트리맵을 활용하여 key값으로 주어진 숫자들의 크기순 정렬을 만들고
        //value 값으로 ArrayList를 활용하여 각 숫자가 나온 위치인덱스를 기록한다.
        TreeMap<Integer, ArrayList<Integer>> tm = new TreeMap<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        //만약 트리맵에 없던 숫자이면 새롭게 key로 추가하고 그 위치를 value에 기록
        //트리맵에 있던 없던 숫자이면 해당 숫자 key의 ArrayList에 그 위치를 추가로 기록
        for(int i = 0 ; i < n ; i++){
            int temp = Integer.parseInt(st.nextToken());
            if(!tm.containsKey(temp)){
                tm.put(temp, new ArrayList<>());
                tm.get(temp).add(i);
            } else tm.get(temp).add(i);
        }
        
        //압축된 좌표값으로 새롭게 담을 nums 배열
        int[] nums = new int[n];
        
        //values 셋을 통해서 가장 낮은 key의 위치배열(ArrayList)부터 끄내서
        //nums배열의 원래 인덱스위치에 기록(i=0, 1, 2, ...)
        int i = 0;
        for(ArrayList<Integer> al : tm.values()){
            for(int num : al){
                nums[num] = i;
            }
            i++;
        }
        
        //출력파트
        for(int j = 0; j < n ; j++){
            sb.append(nums[j]+" ");
        }
        System.out.println(sb.toString());
    }
}