[백준] 18870 좌표 압축.java

문제

수직선 위에 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을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

---

나의 풀이

1. 배열을 두개를 n개의 길이만큼 생성한다음 두개의 배열에 모두 동일하게 입력을 받는다.
2. 그 후 1번 배열은 Arrays.sort() 를 사용해서 정렬을 해주고,
3. 중복이 안되게 해주는 map에 key와 value를 넣어줄건데 key는 배열의 값, value는 rank(몇번째로 큰지)를 넣어주면 된다.
4. 그 후 2번 째 배열과 map을 비교해서 2번째 배열에 해당하는 값을 key와 비교해서 value값을
5. StringBuilder에 더해주면 시간초과도 피해서 출력할 수 있다.

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;
import java.util.Scanner;


public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int[] arr = new int[n]; //정렬용
        int[] answer = new int[n]; //map이랑 비교할 배열용
        Map<Integer, Integer> map = new HashMap<Integer, Integer>();

        //배열 입력받기
        for (int i = 0; i < n; i++) {
            arr[i] = answer[i] = sc.nextInt();
        }

        //배열 오름차순 정렬
        Arrays.sort(arr);
        //-10 -9 2 4 4
        // 0 1 2 3 3
        int rank = 0;

        for (int i : arr) {
            if (!map.containsKey(i)) {
                map.put(i, rank);
                rank++;
            }
        }
        StringBuilder sb = new StringBuilder();
        for (int key : answer) {
            sb.append(map.get(key)).append(" ");
        }
        System.out.println(sb);

    }
}