[JAVA] 좌표 압축 18870번

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

18870번: 좌표 압축

 

어렵지는 않았으나 문제를 잘 읽고 풀어야 하는 문제다.

X'i의 값은 Xi 값보다 작고 서로 다른 값을 가지는 좌표의 갯수이다. 

즉 값이 Xi보다 작더라도 중복이면 1개만 인정한다는 말이다.

 

예시 2번을 보면 다음과 같이 시각화 할 수 있다.

즉. X'i의 값은 Xi좌표보다 왼쪽에 있는 좌표의 갯수를 말하는데. 좌표값이 같다면 여러개 있더라도 하나로만 생각한다는 말이다.

 

 소스코드

package 백준.정렬.좌표압축;

import java.util.Arrays;
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.HashMap;
import java.util.Map;
import java.util.StringTokenizer;
/*
* 1.첫째 줄에 X배열이 크기 N를 입력받는다.
* 2.둘째 줄에 배열 원소의 값들을 공백으로 분리하여 입력받는다.
* 3.
*
*
* */
public class 좌표압축_18870 {
    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];

        StringTokenizer st = new StringTokenizer(br.readLine());
        for(int i=0; i<N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
        int[] sortedArr = arr.clone();
        Arrays.sort(sortedArr);

        Map<Integer,Integer> map = new HashMap<>();

        int index = 0;
        for(int num : sortedArr) {
            if(!map.containsKey(num))
                map.put(num, index++);
        }

        StringBuilder sb = new StringBuilder();
        for(int i=0; i<N; i++){
            sb.append(map.get(arr[i])).append(' ');
        }

        System.out.println(sb);
    }
}