[백준] 18870번 : 좌표 압축 [Java]

#풀이

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));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        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++){
            arr[i] = Integer.parseInt(st.nextToken());
            set.add(arr[i]);
        }
        Map<Integer, Integer> map = new HashMap<>();
        int index = 0;
        for(int i : set){
            map.put(i,index);
            index++;
        }

        int temp;
        for (int j : arr) {
            temp = map.get(j);
            bw.write(String.valueOf(temp) + " ");
        }
        bw.flush();
    }
}

#성능

#정리

처음에는 중복 제거 후 리스트로 변환해 indexOf()로 좌표를 찾았지만, indexOf()는 요소마다 리스트를 순회하므로 O(N²) 시간복잡도가 되어 시간 초과가 발생했다. 이를 Map으로 변경해 값과 압축 좌표를 미리 매핑함으로써 좌표 조회를 O(1)에 할 수 있었고, 전체 시간복잡도를 O(N log N)으로 줄일 수 있었다.