백준 18870 좌표압축

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

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

출력

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

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1 복사

5
2 4 -10 4 -9

예제 출력 1 복사

2 3 0 3 1

예제 입력 2 복사

6
1000 999 1000 999 1000 999

예제 출력 2 복사

1 0 1 0 1 0

 

 

코드

 

입력이 굉장히 크길래 BufferedReader와 BufferedWriter를 사용해서 입출력을 했다

트리맵에 넣으면 오름차순으로 정렬되니 트리맵에 있는 원소 수 만큼 0부터 쭉 가면

그 앞에 몇개의 숫자가 있는지가 나온다 

 

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

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());

       String[] input =  br.readLine().split(" ");

        //중복 제거해서 정렬할 트리맵
       TreeMap<Long, Integer> treeMap = new TreeMap<>();

       for (int i =0; i < n; i++){
           treeMap.put(Long.parseLong(input[i]),0);
       }

        int idx = 0;

       //트리맵 순회하면서 밸류에 자기보다 작은 숫자 갯수를 넣어둠
        for (Map.Entry<Long, Integer> x : treeMap.entrySet()){
            Long x1 = x.getKey();
            treeMap.put(x1,idx++);
        }

        for (int i = 0; i < n; i++){
            bw.write(treeMap.get(Long.parseLong(input[i])) + " ");
        }
        bw.flush();
    }
}