좌표의 크기가 너무 크다면? 좌표 압축 알고리즘

 

[알고리즘 기본 개념]

 

위 문제로 예를 들어보자면 x, y의 좌표는 최대 0,0~2^31, 2^31이다. 

2^31은 int의 바운더리 안에 가깝게 들어오는 값이다. (int는 최대 2^32 = 20억정도)

 

만약, (0,0) 과 (2^31, 2^31) 을 비교하라고 하면 n의 범위를 2^31 로 둘 수 있을까? 시간 초과 결과가 나올 것이다. 

컴퓨터가 1초에 처리할 수 있는 연산은 1억 정도.

 

그래서 인덱스를 이용한 좌표 압축 알고리즘이 있다. 

 

data = [[0, 0], [1, 1], [0, 2], [2, 0], [0, 3], [3, 2], [1, 4], [4, 4], [100, 50], [150, 30]]

 

이렇게 비교가 필요한 좌표가 주어진다면 

x의 좌표와 y좌표를 따로 구분한다. 

xpoint = [0,1,0,2,0,3,1,4,100,150]

ypoint = [0,1,2,0,3,2,4,4,50,30]

 

그리고 중복을 제거한다. (중복이 있을 필요가 없다.)

xpoint = [0,1,2,3,4,100,150]

ypoint = [0,1,2,3,4,50,30]

 

중복을 제거한 각 벡터를 오름차순으로 정렬한다. 

xpoint = [0,1,2,3,4,100,150]

ypoint = [0,1,2,3,4,30,50]

 

이제 각 좌표를 탐색하면서 인덱스로 대치해준다. 

data[0][0] == x[0] (0)

data[0][0] = 0;

 

data[0][1] == y[0] (0)

data[0][1] = 0

 

data[1][0] == x[1] (1)

data[1][0] = 1;

 

....

 

data[9][0] == x[6]

data[9][0] = 6;

 

data[9][1] == y[5]

data[9][1] = 5;

 

이렇게 하면 

0,0	0 0
1,1	1 1
0,2	0 2
2,0	2 0
0,3	0 3
3,2	3 2
1,4	1 4
4,4	4 4
100,50	5 6
150,30	6 5

 

이렇게 좌표가 압축된다.

 

    for (int i =0; i < data.size(); i++) {
        xp.push_back(data[i][0]);
        yp.push_back(data[i][1]);
        
    }
    
    unordered_set<int> uniqXp(xp.begin(), xp.end()); //중복 제거
    unordered_set<int> uniqYp(yp.begin(), yp.end()); //중복 제거
    
    xp.clear(); yp.clear(); //중복 제거된 값을 넣기 위해 clear
    
    xp.assign(uniqXp.begin(), uniqXp.end());
    yp.assign(uniqYp.begin(), uniqYp.end());
    
    sort(xp.begin(), xp.end());
    sort(yp.begin(), yp.end());
    
    //좌표 압축 
    int x = 0, y = 0;
    for (int i = 0; i < data.size(); i++) {
        for (int j = 0; j < xp.size(); j++) {
            if (data[i][0] == xp[j]) {
                x = j;
                data[i][0] = x; //좌표를 인덱스로 대체한다.
                break;
            }
        }
        for (int j = 0; j < yp.size(); j++) {
            if (data[i][1] == yp[j]) {
                y = j;
                data[i][1] = y; //좌표를 인덱스로 대체한다.
                break;
            }
            
        }
        
    }