백준 정렬 - 18870번 : 좌표 압축

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

18870번: 좌표 압축

---

import java.util.*;
import java.io.*;
public class Main {
	public static int[] sorted;
	public static void main(String[] args) throws IOException{
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] a = new int[n];
        int[] b = new int[n];
        for(int i=0; i<n; i++){
            a[i] = sc.nextInt();
            b[i] = a[i];
        }
        sorted = new int[n];
        merge_sort(a,0,n-1);
        HashMap<Integer,Integer> hm = new HashMap<>();
        int idx = 0;
        for(int i=0; i<n; i++) {
        	if(hm.get(a[i])==null) {
        		hm.put(a[i], idx++);
        	}
        }
        for(int i=0; i<n; i++) {
        	b[i] = hm.get(b[i]);
        }
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        for(int i=0; i<sorted.length; i++) {bw.write(b[i]+"\n");}
        bw.close();
    }
	public static void merge_sort(int[] a, int i, int j) {
		if(i==j) return;
		int mid = (i+j)/2;
		merge_sort(a,i,mid);
		merge_sort(a,mid+1,j);
		merge(a,i,mid,j);
	}
	public static void merge(int[] a,int i, int mid, int j) {
		int idx = i;
		int start = i;
		int target = mid+1;
		while(start<=mid&&target<=j) {
			if(a[start]<=a[target]) {
				sorted[idx++] = a[start];
				start++;
			}
			else if(a[start]>a[target]){
				sorted[idx++] = a[target];
				target++;
			}
		}
		
		while(start<=mid) {
			sorted[idx++] = a[start];
			start++;
		}
		while(target<=j) {
			sorted[idx++] = a[target];
			target++;
		}
		for(int k = i; k<=j; k++) {
			a[k] = sorted[k]; 
		}
	}
}