[백준 알고리즘] 18870번 : 좌표 압축

문제

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

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.HashMap;
import java.util.StringTokenizer;

public class BOJ_18870 {
    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> rankMap = new HashMap<>();

        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        for (int i = 0; i < N; i++) {
            sorted[i] = origin[i] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(sorted);

        int rank = 0;
        for (int i : sorted) {
            if (!rankMap.containsKey(i)) {
                rankMap.put(i, rank);
                ++rank;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i : origin) {
            int answer = rankMap.get(i);
            sb.append(answer).append(' ');
        }
        System.out.println(sb);
    }
}

풀이 및 느낀점

배열에 입력받은 각 원소값에 대해서 순위를 매겼다. 각 원소 중에서 가장 작은 값을 0순위로 매기고 2번째로 작은 값은 1순위로 매기는 방식으로 문제에 접근했다.

입력받은 값을 오름차순으로 정렬했다. 가장 낮은 값이 높은 순위를 갖는데, 이를 hashMap을 사용하여 ranking을 매겼다. 중복된 원소가 들어가지 않도록 조건문을 만들어 저장했다.

윈본 배열을 차례대로 순회하면서 hashMap에 있는 key(원소)에 대한 value(랭킹)을 갖고 온다.

참고자료