[알고리즘] 좌표 압축 개념 (대소 관계로 정렬)

좌표 압축

💡 👍🏻 수의 범위가 매우 큰 상태에서 수의 값과 상관 없이 숫자의 대소 관계만 알면 될 때 이용하는 알고리즘이다.

• ✨ 수의 범위를 확 줄일 수 있다.
• 수의 값보다 크고 작은 순서가 중요하다.

 

좌표 압축 원리

좌표 압축은 정렬과 이분 탐색이 필요하다.

1. 입력 받은 배열을 압축용 배열에 오름차순 정렬한다. (정렬 ⭐)
2. 압축용 배열에서 중복 요소는 제거한다. (중복 제거 ⭐)
3. 압축용 배열에 새로운 인덱스를 부여한다. (순서를 주는 것)

 

좌표 압축 예시

int [] arr = {2, 4, -10, 4, -9};
//오름차순 정렬
int [] arr_tmp = {-10, -9, 2, 4, 4}; 
//중복요소를 제거한다.
{-10, 9, 2, 4}
[0] [1] [2] [3]

//원래 배열에 압축용 배열의 index 를 붙이면 끝. 
-> 2, 3, 0, 3, 1

입력 받은 배열의 값과 일치하는 압축용 배열의 index 값을 가져온다.

⇒ 크고 작음에 따라 새로운 순서가 붙었다.

 

 

핵심 ✨

1. 좌표 압축하고자 하는 배열을 '정렬'한다. 
2. 중복되는 값은 '제거' 한다. (어차피 같은 값은 순위가 무의미하다.)
3. 압축 배열의 순위를 정해준다. (index 를 정해준다.)
4. 기존 배열에 압축 배열에서 정해진 순위를 붙여준다.