개발하는 두더지

좌표 압축 알고리즘 본문

알고리즘

좌표 압축 알고리즘

덜지 2018. 4. 19. 22:30

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

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

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


문제에서 좌표는 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


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


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


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


Comments