좌표 압축

 값의 대소 관계만 필요하다면 수를 바꾸어 사용할 수 있다.

 예를 들어 [0, 1, 5, 6, 11] 이런 좌표라면 [0, 1, 2, 3, 4]로 바꿀 수 있고, [0, 100, 150, 50, 175, 50, 50] 이런 좌표라면 [0, 2, 3, 1, 4, 1, 1]로 바꿀 수 있다.

 방법은 크게 2가지가 있다.

• vector의 unique 값을 지우고 lower_bound로 해당 값을 찾는 방법
• set으로 중복을 지우고 map으로 압축된 좌표를 mapping하는 방법

 

1. vector의 unique 값을 지우고 lower_bound로 찾는 방법 : O(nlogn)

void gridCompress(vector<int> &arr){
    vector<int> temp(arr.size());
    for(int i = 0; i<arr.size(); i++){
        temp[i] = arr[i];
    }
    sort(temp.begin(), temp.end());
    temp.erase(unique(temp.begin(), temp.end()), temp.end());
    for(int i = 0; i<arr.size(); i++){
    	arr[i] = lower_bound(temp.begin(), temp.end(), arr[i]) - temp.begin();
    }
}

 

2. set으로 중복을 지우고 map으로 값을 mapping하는 방법 : O(nlogn)

void gridCompress(vector<int> &arr){
	set<int> temp;
	for(int i = 0; i<arr.size(); i++){
		temp.insert(arr[i]);
	}

	int i = 0;
   	map<int, int> mapper;
	for(int elem : temp){
		mapper[elem] = i++;
	}

	for(int i = 0; i<arr.size(); i++){
    	arr[i] = mapper[arr[i]];
    }
}

 

 기억만 해 두고, 그때그때 좋은 것을 사용하자. 그러나 기본적으로는 위의 것이 더 빠르다!