[알고리즘] 좌표 압축(백준18870번)_실버2_좌표압축, 해시맵

문제링크

📝 문제

수직선 위에 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

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

예제 입력 2

6
1000 999 1000 999 1000 999

예제 출력 2

1 0 1 0 1 0

---

🔍 정답

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    public static void main(String[] args) throws IOException {

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        int[] origin = new int[N]; // 좌표가 담긴 원 배열
        int[] sorted = new int[N]; // 원 배열을 오름차순으로 정렬할 배열

        /**
         * origin 과 sorted 배열에 모두 값을 담아준다.
         * sorted 배열은 요소들을 오름차순으로 정렬해서 낮은 수부터 랭크를 순서대로 매겨주기 위함
         * 예시 : origin = sorted = [2, 4, -10, 4, -9]
         */
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            origin[i] = sorted[i] = Integer.parseInt(st.nextToken());
        }

        /**
         * origin = [2, 4, -10, 4, -9]
         * sorted = [-10, -9, 2, 4, 4]
         */
        Arrays.sort(sorted);

        /**
         * 해시맵에 낮은 수부터 넣으며 rank를 매겨준다.
         * 배열의 수들은 key가 되고 랭크는 value가 된다.
         * 이 때, 이미 랭크가 매겨진 수가 중복되어서 또 나온다면 스킵한다!
         * rankingmap = {-10=0, -9=1, 2=2, 4=3}
         */
        HashMap<Integer, Integer> rankingMap = new HashMap<>();
        int rank = 0;
        for (int value : sorted) {
            if (!rankingMap.containsKey(value)) {
                rankingMap.put(value, rank);
                rank++;
            }
        }

        /**
         * 이제 origin 배열의 순서대로 value값(rank)을 뽑으면 된다!
         * origin 배열의 0번 인덱스인 2가 key값으로 들어가면, 대응하는 value값인 2가 출력되고
         * 그 다음 1번 인덱스인 4가 key값으로 들어가면, 대응하는 value값인 3이 출력
         * 그 다음 2번 인덱스 -10이 key값으로 들어가서, 대응되는 value값 0이 출력되는 식이다.
         */
        StringBuilder sb = new StringBuilder();
        for (int key : origin) {
            int ranking = rankingMap.get(key);
            sb.append(ranking).append(" ");
        }

        System.out.println(sb);
    }
}

참고

• 좌표 압축의 개념을 요약하면,
• 수의 범위가 매우 큰 상황에서 수의 값과 무관하게 요소들 사이의 대소만 알면 될 경우, 각 요소들의 순위 를 매겨서 대소를 표현하는 것이다.
• 데이터의 범위가 매우 크거나 단순화할 필요가 있을 때 사용한다고 한다.

---

관련 자료

• 좌표 압축 개념 그림으로 설명