[백준/Java] 18870 좌표 압축

문제

https://www.acmicpc.net/problem/18870

풀이방법

중복이 없어야해서 Set을 썼는데 정렬이 필요했다...

그래서 이전에 스터디할 떄 정리한 TreeSet을 사용하였다

그리고 set의 인덱스를 접근하려했는데 해당 시간복잡도가 높아서 시간초과가 났다

해쉬맵을 사용하면 N(1)이 가능..

풀이

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));
        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        TreeSet<Integer> set = new TreeSet<>();
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            set.add(arr[i]);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int idx = 0;
        for (int num : set) {
            map.put(num, idx);
            idx++;
        }
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i<N; i++) {
            sb.append(map.get(arr[i])).append(" ");
        }
        System.out.println(sb);
    }
}