(백준) 18870호: 좌표압축

by

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

18870호: 좌표압축

수직선에는 N개의 좌표 X1, X2, …, XN이 있습니다. 이 좌표에 좌표 압축을 적용하려고 합니다. Xi의 좌표 압축 결과 X’i의 값은 Xi > Xj를 만족하는 개별 좌표의 수와 같아야 합니다. X1, X2, …, XN에 대한 링크

www.acmicpc.net

문제 설명

이런 문제는 처음이라 문제를 이해하지 못한 채 검색을 해봤습니다. 알고 보니 좌표 압축이라는 알고리즘이 아니라 범주가 있습니다. 다음 글은 제가 참고한 글입니다.

https://st-lab.279

(백준) #18870: 좌표 압축 – JAVA(Java)

https://www.acmicpc.net/problem/18870 #18870: 좌표 압축 세로선에 N개의 좌표 X1,X2,…,XN이 있습니다. 이 좌표에 좌표 압축을 적용하려고 합니다. Xi의 좌표축소 결과 Xi > Xj로 X’i의 값이 달라지게 된다.

st-lab.tistory.com

자세한 설명은 관련 기사를 참조하십시오.

해결 방법

위의 기사를 바탕으로 다음 코드를 작성했습니다.

import java.io.*;
import java.util.*;

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);
        HashMap<Integer, Integer> mapForRank = new HashMap<>();
        
        String() Xs = br.readLine().split(" ");
        
        for (int i = 0; i < N; i++) {
            origin(i) = sorted(i) = Integer.parseInt(Xs(i));
        }
        
        Arrays.sort(sorted);
        
        int rank = 0;
        for (int v: sorted) {
            if (!mapForRank.containsKey(v)) {
                mapForRank.put(v, rank);
                rank++;
            }
        }
        
        StringBuilder sb = new StringBuilder();
        
        for (int key: origin) {
            int ranking = mapForRank.get(key);
            sb.append(ranking).append(' ');
        }
        
        System.out.print(sb);
    }
}