[알고리즘] 좌표 압축

치토스 선배 강의 듣고 씀.

 

---

좌표 압축

좌표의 범위가 막 ≤ 1,000,000,000으로 큰 경우가 있다. 이런 경우에 arr[1000000000] 같은 배열을 선언하면 당연히 터져버린다.

 

[BOJ] 가로 블록 쌓기 문제 같은 경우 0 ≤ Wi + Di ≤ 2,000,000,000로 좌표 자체의 범위는 크지만, 들어오는 블록의 개수는 100,000개다. 즉 좌표로서 들어오는 수의 종류는 최대 200,000개 라는 뜻이다. 200,000개는 배열로 만들 수 있다.

만약 들어오는 좌표의 종류가 {1, 23434, 9495444, 124, 8, 249833876, 23434}이라면 이를 순서대로 정렬하고 {1, 8, 124, 23434, 23434, 9495444, 249833876}, 중복을 제거해  {1, 8, 124, 23434,  9495444, 249833876} 이라는 새 좌표 배열을 만든다.

 

sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

 

그러면 저 수들을 1은 0, 8은 1, 124는 2... 처럼 새 배열의 인덱스로 치환할 수 있다. 이 새 배열은 원래 배열의 종류 만큼의 개수를 갖게 되므로, 수의 범위가 커도 종류가 작으면 압축할 수 있다.

실제로 변환할 때는 좌표 배열에서 lower_bound로 해당 수의 인덱스를 찾아준다.

 

lower_bound(v.begin(), v.end(), num) - v.begin()

 

오름차순으로 정렬된 N개의 수열에서 이분탐색으로 원하는 값을 찾는 시간복잡도는 O(logN)이니까 lower_bound로 찾아주면 O(logN)만에 찾을 수 있다. 😁

 

tmi) 원래 이런 문제가 나오면, map을 이용해야 하는 줄 알았는데 unique 함수를 잘 이용하면 벡터에서 중복값들을 지울 수 있다는 것을 알게 되었다!

---

관련 문제

[BOJ] 가로 블록 쌓기

18407번: 가로 블록 쌓기