좌표 압축 알고리즘

좌표 압축 알고리즘 언제사용할까?

순위가 중요한 알고리즘에서 입력값의 개수보다 입력값의 범위가 클때 사용한다.

예를 들면 캠핑 문제에 적용할 수 있다. ( 프로그래머스 카카오 캠핑 문제 풀러가기 )

문제에서 좌표는 0 이상 2^31 이하의 값을 가질 수 있지만 최대 입력값은 5000이다.

문제의 특성상 대각에 위치한 두 좌표를 이용해 직사각형을 만들고 그 직사각형안에 또 다른 좌표가 있는지 확인해야 한다.

아래와 같은 입력값이 있다고 하자.

int pin[][] = new int[][]{{0,0}, {1,1}, {0,2}, {2,0}, {0,3}, {3,2}, {1,4}, {4,4}, {100, 50}, {150, 30}};

0,0 ~ 4,4 사이는 1칸씩 차이라 공간적인 문제가 없지만 

0,0 ~ 150,30 을 비교하기 위해서는 150 * 30의 공간을 탐색해야 한다.

0,0 ~ 2^31, 2^31 라면  2^31 * 2^31의 공간을 탐색한다. 

좌표가 공간내에 많이 차지한다면 필요한 검색이겠지만 앞부분에 몰려있다면 나머지 부분은 불필요한 공간 탐색이다.

좌표 압축을 통해

0,0 ~ 150,30  -> 0,0 ~ 6,5 를 탐색하게 된다면 시간적, 공간적으로 상당히 효율적이다.

소스

package com.example.lib;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashSet;

public class myClass {
    public int solution(int n, int[][] data) {
        int answer = 0;

        for(int i = 0; i < data.length; i++) {
            System.out.println(Arrays.toString(data[i]));
        }

        // 2개의 ArrayList에 x, y 좌표값을 담음
        ArrayList<Integer> xList = new ArrayList<>();
        ArrayList<Integer> yList = new ArrayList<>();
        for(int i = 0; i < n; i++) {
            xList.add(data[i][0]);
            yList.add(data[i][1]);
        }

        // x, y 좌표 중복제거
        ArrayList<Integer> uniqueXList = new ArrayList<>(new HashSet<>(xList));
        ArrayList<Integer> uniqueYList = new ArrayList<>(new HashSet<>(yList));

        // 오름차순 정렬
        Collections.sort(uniqueXList);
        Collections.sort(uniqueYList);

        for(int i = 0; i < n; i++) {
            int x = uniqueXList.indexOf(new Integer(data[i][0]));
            int y = uniqueYList.indexOf(new Integer(data[i][1]));

            data[i][0] = x;
            data[i][1] = y;
        }

        System.out.println();
        for(int i = 0; i < data.length; i++) {
            System.out.println(Arrays.toString(data[i]));
        }

        return answer;
    }

    public static void main(String[] args) {
        myClass mc = new myClass();
        int pin[][] = new int[][]{{0,0}, {1,1}, {0,2}, {2,0}, {0,3}, {3,2}, {1,4}, {4,4}, {100, 50}, {150, 30}};
        System.out.println(mc.solution(pin.length, pin));
    }
}

결과

# 좌표압축 전

[0, 0]

[1, 1]

[0, 2]

[2, 0]

[0, 3]

[3, 2]

[1, 4]

[4, 4]

[100, 50]

[150, 30]

# 좌표압축 후

[0, 0]

[1, 1]

[0, 2]

[2, 0]

[0, 3]

[3, 2]

[1, 4]

[4, 4]

[5, 6]

[6, 5]

참고

카카오 코드 페스티벌 캠핑 문제 상세 풀이

카카오 코드 페스티벌 캠핑 문제 상세 풀이2

백준 알고리즘 사이트 세그먼트 트리 상세 설명

좌표압축 알고리즘 기본 개념

좌표압축 알고리즘 간단 예제