[코딩테스트] 백준 18870번 좌표 압축 - JAVA

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

Problem 💻

문제

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

 

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

 

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

 

 

Solution 💡

이 문제는 짧은 내용과 좌표 압축이라는 단어 때문에 어렵게 느껴진다. 문제에서 주어진 조건을 잘 이해하는 것이 중요하다.

X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

문제에 주어진 조건을 보면 `Xi`는 본인을 의미하며, `Xj`은 본인을 제외한 나머지 값들을 의미한다. 나머지 X값 중 본인보다 작은 수가 몇개이며, 중복 수는 제외한다는게 조건이다.

주어진 입력값을 오름차순 정렬한다면, `Xj`의 개수가 `0,1,2..` 순으로 순차적으로 증가되게 할 수 있다. `(Xi , Xj의 개수)` 형태의 자료구조가 필요하므로 `Map`을 이용하였고 해당 맵에 이미 `key` 값이 있는 경우 동작이 되지 않게 처리하였다.

 

if (!map.containsKey(num)) {
    map.put(num, count);
    count++;
}

단, 주의해야 할 점은 출력값은 정렬 전 값 기준으로 출력되야하므로 배열을 정렬하는 값을 기존 입력값을 담은 배열을 `clone()`을 이용해 복사하여 사용하였다.

 

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

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());
        StringTokenizer st = new StringTokenizer(br.readLine());

        int[] x = new int[n];
        for (int i = 0; i < n; i++) {
            x[i] = Integer.parseInt(st.nextToken());
        }

        int[] sorted = x.clone();
        Arrays.sort(sorted);

        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for (int num : sorted) {
            if (!map.containsKey(num)) {
                map.put(num, count);
                count++;
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int num : x) {
            sb.append(map.get(num)).append(" ");
        }

        System.out.println(sb);
    }
}