[실버 2] 18870번 좌표 압축

문제 링크 : https://www.acmicpc.net/problem/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

코드

import java.util.*;
import java.io.*;
 
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());
		int[] input = new int[N]; // 입력 받은 순서 알기 위한 배열
		int[] arr = new int[N];   // 정렬하기 위한 배열
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		
		StringTokenizer st = new StringTokenizer(br.readLine());
		for(int i=0; i<N; i++) {
			int num = Integer.parseInt(st.nextToken());
			input[i] = num;
			arr[i] = num;
		}
		
		Arrays.sort(arr);
		
		map.put(arr[0], 0);
		int rank = 1; // 순서 변수
		int index = 1;
		
		while(index < N) { // N보다 작을 때까지
			if(arr[index] != arr[index - 1]) {  // 정렬했기 때문에 앞 뒤 중복이 아닐 때
				map.put(arr[index], rank);
				rank++;
			}
			index++;  // 중복이면 순서는 그대로 인덱스만 +1
		}
		
		for(int i=0; i<N; i++) sb.append(map.get(input[i])).append(" ");
		
		System.out.println(sb);
	}
}