[Baekjoon] 18870번: 좌표 압축

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

18870번: 좌표 압축

문제 설명

이런 문제는 처음 접해봐서 문제 이해부터 못하고 검색해보았다. 알고 보니 좌표 압축이라는 알고리즘이 있는 게 아니라 하나의 카테고리였다. 다음 글이 필자가 참고한 글이다.

https://st-lab.tistory.com/279

[백준] 18870번 : 좌표 압축 - JAVA [자바]

 

자세한 설명은 해당 글에서 대신한다.

주의할 점은 두 가지 조건이 있다.

1. 낮은 값이 높은 순위를 갖는다(가장 높은 순위는 0이다).
2. 중복되는 원소는 같은 순위를 갖는다.

낮은 값이 높은 순위를 갖는다는 말은 정렬을 활용하면 해결할 수 있을 거라는 뜻이다. 또한 중복되는 원소는 같은 순위를 갖기 때문에 중복 제거에 특화된 자료구조인 Map 또는 Set을 활용할 수 있을 것이다. 필자는 HashMap을 사용했다.

풀이 방법

위 글을 참고하여 다음과 같은 코드를 작성했다. 자세한 설명은 주석으로 달았다.

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
        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);
    }
}