백준 18870: 좌표 압축(JAVA)/ 좌표 압축 알고리즘

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

18870번: 좌표 압축

 

알고리즘 분류를 보면 정렬과 좌표 압축으로 분류가 되어있다. 

 

 

좌표압축 알고리즘

-좌표(문제)의 범위가 너무 넓을 때 각 좌표에 인덱싱을 하여 좌표 사이 간격을 없앰

-중요한 구간이나 숫자만 갖고 가는 것

-불필요한 좌표를 날리기 or 데이터 자체를 압축 하기

-대소관계만 알면 될 때 사용함 데이터를 정렬해서 다시 순서를 부여

 

HashMap을 이용하여 인덱싱을 하였다. 배열을 입력 받고 배열 복사본을 만들어 정렬한 후 Map의 key로 원소를 사용하고 value로 해당 원소의 순위를 저장한다. 

원본 배열에서 Map.get을 통해 해당 원소의 순위를 알아낼 수 있다. 

import java.util.*;

public class Main {
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();

		int[] arr = new int[n];
		for(int i=0; i<n; i++)
			arr[i] = sc.nextInt();
		
		int[] sorted = arr.clone();
		Arrays.sort(sorted);
		
		HashMap<Integer, Integer> map = new HashMap<>();
	
		int i=0;
		for(int a: sorted) {
			if(!map.containsKey(a))
				map.put(a, i++);
		}
		
		StringBuilder sb = new StringBuilder();
		for(int a: arr) {
			sb.append(map.get(a)+" ");
		}
		System.out.println(sb);
	}
}