[백준/Java] 18870번 :: 좌표 압축

| 문제

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

 

| 제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

| 풀이

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));
        StringBuilder sb = new StringBuilder();

        int N = Integer.parseInt(br.readLine());
        int[] arr = new int[N];
        int[] copy = new int[N];

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

        Arrays.sort(copy);

        Map<Integer, Integer> map = new HashMap<>();
        int count = 0;
        for(int i=0; i<N; i++)
        {
            if(!map.containsKey(copy[i])) {
                map.put(copy[i], count++);
            }
        }

        for(int i=0; i<N; i++)
        {
            sb.append(map.get(arr[i])).append(" ");
        }

        System.out.println(sb);

    }
}

 

| 정리

문제를 풀기 전에 좌표 압축이 뭔지 먼저 찾아봤다.

예제로만 봤을 때는 자기 자신보다 작은 수가 몇개 있는지 찾는건가 싶었는데, 좌표를 정렬하고 이를 순서로 표현한 것이라고 한다.

먼저, 배열과 복사본 배열에 입력 값을 저장하고 복사본을 오름차순으로 정렬을 해준다.

for문을 수행하면서 map에 copy[i]값이 없으면 map.put 코드가 실행되도록 조건문을 수행한다.

두 번째 for 문에서는 map에서 arr[i]와 일치하는 key의 value값을 가져와서 sb에 append한다.