좌표압축(18870)

https://www.acmicpc.net/problem/18870 만약 정확한 값이 필요 없고 값의 대소 관계만 필요하다면, 모든 수를 0 이상 N 미만의 수로 바꿀 수 있습니다.

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

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

출력

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

5 2 4 -10 4 -9 => 2 3 0 3 1

6 1000 999 1000 999 1000 999 => 1 0 1 0 1 0

아아.. 문제의 의미는 각 원소가 해당 원소보다 작은게 원소가 몇개 인지를 카운팅하는 거구나

package me.kdshim.kdd_j.Baekjoon;

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;
import java.util.stream.Collectors;

public class sorting_18870 {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int cnt = Integer.parseInt(br.readLine());

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

        int sorted[] = arr.clone();
        //이건 시간복잡도가 시간복잡도가 nlogn
        Arrays.sort(sorted);

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

        int idx = 0;
        for(int i=0; i<cnt; i++){
            if(!map.containsKey(sorted[i])){
                map.put(sorted[i], idx++);
            }
        }

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

        System.out.println(sb);
    }
}

음 원래는 인덱스가 몇인지 일일이 확인해서 그 인덱스가 몇 번째인지도 확인해서 해당 인덱스를 저장하는 배경도 따로 만들어보려고 했다 근데 생각보다 쉽지 않더라구요.. 그래서 맵으로 해당 값에 대한 인덱스번째를 저장하는 맵을 사용해서 맵을 사용해서 구현함

살짝 소름인건.. 처음에는 stream.sort으로 갔었다는거... 이걸 기억못하다니... 기억 잘하자 배열[] 에서는 Arrays.sort()을 통해서 sorting이 가능하다는점