정렬: 좌표 압축

Algorithm : 좌표 압축

: 좌표의 범위가 너무 큰 경우 인덱싱으로 좌표 사이 갭을 없애는 기법으로, 데이터를 정렬해서 다시 순서를 부여하는 것

 

좌표 압축이 필요한 이유

일차원 직선상에 N=10만개의 점이 있고 [x, y] 구간의 점 개수를 출력하는 쿼리가 M개 있을 때, 점의 범위나 x, y의 범위가 [-10⁹, 10⁹] 라면 세그먼트 트리를 구성하려고 했을 때 일반적으로 문제에서 주어지는 메모리 256MB로는 해결이 불가능하다. 하지만 점의 개수에 비해 점의 범위가 훨씬 넓어 sparse 하다는 점을 이용한다면 각 점의 좌표마다 인덱싱을 해, 정렬된 순서로 번호를 매김으로써 답을 구할 수 있다.

 

좌표 압축 알고리즘 코드

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

18870번: 좌표 압축

 

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 Main {
	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int n = Integer.parseInt(br.readLine());
		int[] coordinate_arr = new int[n];
		
		HashMap<Integer, Integer> map = new HashMap<Integer, Integer>();
		int[] temp_arr = new int[n];
		
		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		
		for(int i = 0; i < n; i++) {
			
			coordinate_arr[i] = Integer.parseInt(st.nextToken());
			temp_arr[i] = coordinate_arr[i];
			
		}
		
		Arrays.sort(temp_arr);
		// 정렬
		
		int index = 0;
		
		for(int i = 0; i < n; i++) {
			
			if(!map.containsKey(temp_arr[i])) {
				map.put(temp_arr[i], index++);
				// 정렬된 배열에 새로운 인덱스를 부여
			}
			
		}
		
		StringBuilder sb = new StringBuilder();
		
		for(int i = 0; i < n; i++) {
			if(map.containsKey(coordinate_arr[i])) {
				
				sb.append(map.get(coordinate_arr[i])).append(" ");
				// 원래의 배열에 좌표 압축을 적용한 결과를 출력
				
			}
		}
		
		System.out.println(sb);
		
	}

}

 

---

 

좌표 압축 참고 사이트

• 좌표 압축 알고리즘 : 범위가 클 때 어떻게 공간을 줄일까요?
• 좌표 압축(Coordinate compression)