[JAVA] 백준 18870번 좌표 압축

문제

 

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

입력

 

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

출력

 

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

입력예제

 

5
2 4 -10 4 -9

 

출력예제

 

2 3 0 3 1

 

풀이

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


public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // 숫자 입력받기
        int n = Integer.parseInt(bf.readLine());

        int[] arr = new int[n];

        // 배열 안에 입력 받기
        for (int i = 0; i < 1; i++) {
            // split 로 잘라서 arr 배열 안에 넣기
                String[] x = bf.readLine().split(" ");
            for (int j = 0; j < n; j++) {
                arr[j] = Integer.parseInt(x[j]);
            }
        }

        // 배열 복사 후 오름차순. 중복제거
        int[] copyArr = arr.clone();
        Arrays.sort(copyArr);
        copyArr = Arrays.stream(copyArr).distinct().toArray();



        // hashmap. key값으로 value 출력
        HashMap<Integer, Integer> ascArr = new HashMap<>();
                for (int i = 0; i < copyArr.length; i++) {
            ascArr.put(copyArr[i],i);
        }


        // 출력
        for (int i = 0; i < arr.length; i++) {
            bw.write(ascArr.get(arr[i]) + " ");
        }

        bw.flush();
        bw.close();
    }
}

 

 

 

for (int i = 0; i < arr.length; i++) {
bw.write(ascArr.indexOf(arr[i]) + " ");
}

 

원래 위 코드처럼 오름차순 한 배열의 인덱스를 빼오는 코드를 짰는데 시간초과가 떴다.

 

indexOf가 O(n) 이고 , for문도 O(n) 시간 복잡도를 가지는데 

위 코드는 for문 안에 indexOf가 있으니 O(n²)의 시간복잡도를 가지게 되어 시간초과가 뜬다.

 

반면 hashmap의 get 함수는 O(1) 의 시간복잡도를 가지기 때문에 hashmap을 써서 시간초과 없이 풀 수 있다.

 

 

 

 

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

18870번: 좌표 압축