[백준 18870] 좌표 압축(Java)

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

18870번: 좌표 압축

좌표 압축 문제

좌표 압축을 적용한 결과를 출력하는 문제

 

사용 알고리즘

# 정렬

📌문제 접근 포인트

1. 좌표 압축의 개념에 대해서 먼저 생각해보자. 좌표 압축은 쉽게 생각하면 중복을 제거하여 오름차순 정렬 후, 해당 순서 인덱스 값을 가져오란 뜻이다.
예를 들어 예제를 좌표 압축을 적용하면
2 4 -10 4 -9를 생각해보면 중복을 제거해서 오름차순 정렬하면 -10 -9 2 4를 얻을 수 있다.
여기서 -10, -9, 2, 4에 각각 해당하는 인덱스 0, 1, 2, 3을 기존의 값에 대입하면 2, 3, 0, 3, 1을 얻을 수 있다.
2. 해당 문제를 해결하기 위해 배열을 선언해서 순서대로 집어 넣은 후, 해당 배열의 복사본을 남겨두자. 그러고 원본을 오름차순 정렬하여 HashMap을 이용해 순서대로 넣어주면서 중복을 제거하자.
3. 복사한 배열과 HashMap의 값을 비교해서 출력하면 성공

⚙ 내가 푼 정답 코드

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));
        int N = Integer.parseInt(br.readLine());
        int count = 0;
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        int[] nums = new int[N];
        for (int i = 0; i < N; i++) {
        	nums[i] = Integer.parseInt(st.nextToken()); 
        }
        int[] origin = nums.clone();
        Arrays.sort(nums);
        StringBuilder sb = new StringBuilder();
        HashMap<Integer, Integer> x = new HashMap<>();
        for (int i = 0; i< N; i++) {
        	if (!x.containsKey(nums[i])) {
        		x.put(nums[i], count++);
        	}
        }
        for (int i = 0; i < N; i++) {
        	sb.append(x.get(origin[i])).append(" ");
        }
        System.out.println(sb);
    }
}