[백준/JAVA] 18870번 좌표 압축

• 좌표 압축
  https://www.acmicpc.net/problem/18870

1. 문제

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

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

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

2. 문제 접근

1) 첫째 줄에 좌표의 개수 N을 입력받는다.
2) N만큼 좌표를 입력받아서 배열에 저장한다.
3) 정렬되기 전의 배열이 후에 필요하기 때문에 배열을 하나 복사하여 만들어둔다.
4) 병합정렬을 이용하여 배열을 정렬한다.
5) 해쉬맵을 이용하여 정렬된 수와 해당하는 인덱스를 저장한다. 이 때, 이미 저장된 수는 저장하지 않는다.
6) 원본 배열을 순회하면 해당하는 해쉬맵 value 값을 출력한다.

3. 코드

import java.io.IOException;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.HashMap;
import java.util.StringTokenizer;

public class Main {
    static int data[];
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        int arr[] = new int[N];
        data = new int[N];

        StringTokenizer st = new StringTokenizer(br.readLine());
        StringBuilder sb = new StringBuilder();
        int num[] = new int[N];
        for(int i=0;i<N;i++) {
            arr[i] = Integer.parseInt(st.nextToken());
            num[i] = arr[i];

        }
        MergeSort(arr, 0, N-1);
        int arrayed[] = new int[N];
        int t= 1;
        HashMap<Integer,Integer> hash = new HashMap<Integer,Integer>();
        for(int i=0;i<N;i++) {
            hash.put(arr[0], 0);
            if(i>0 && arr[i] !=arr[i-1]) {
                hash.put(arr[i], t);
                t++;
            }
        }
        for(int i=0;i<N;i++) {
            sb.append(hash.get(num[i])).append(" ");
        }

        System.out.print(sb);
    }

    static void Merge(int arr[], int start, int mid, int end) {
        int i = start;
        int j = mid+1;
        int k = start;

        while(i<=mid && j<=end) {
            if(arr[i]< arr[j]) {
                data[k] = arr[i];
                i++;
            }
            else {
                data[k] = arr[j];
                j++;
            }
            k++;
        }
        if(i>mid) {
            for(int t=j;t<=end;t++) {
                data[k] = arr[t];
                k++;
            }
        }
        else {
            for(int t=i;t<=mid;t++) {
                data[k] = arr[t];
                k++;
            }
        }
        for(int t=start; t<=end;t++) {
            arr[t] = data[t];
        }
    }

    static void MergeSort(int arr[], int start, int end) {

        if(start<end) {
            int mid = (start + end)/2;

            MergeSort(arr, start, mid);
            MergeSort(arr, mid+1, end);
            Merge(arr, start, mid, end);
        }
    }

}