좌표압축

좌표압축

만약 x축의 좌표가 [0 ,1 ,2 ,3 ,100 ,150]과 같이 주어졌을 때, 0~3은 각 1씩 차이라 크게 문제 되지 않지만
100과 150을 탐색하기 위해서는 100까지, 150까지 탐색해야하는 문제점이 있다.
다시말해 4~99, 101~149는 쓰지 않는데 탐색하고 있는 시간낭비를 하고 있는 것이다.
숫자의 갭차이가 크게 늘어난다면 시간낭비는 더욱 늘어날 것이다.
이때 사용하는것이 좌표 압축이다.

좌표압축 사용

0 ,1 ,2 ,3 ,100 ,150 을 0 ,1 ,2 ,3은 그대로 100을 4로 150을 5로 가정하고 비교한다면 매우 시간이 절약될 것이다.
그래서 0, 1, 2, 3, 100, 150 => 0, 1, 2, 3, 4, 5로 나타낼 수 있다.

구현 방법

먼저 값을 배열로 받고 중복되는 값은 필요 없으니 집합형태로 만들어 준다.
다음에 정렬을 통해 오름차순으로 만들고 각 값들의 인덱스를 좌표압축에 사용하면 된다.

 

파이썬 : https://smhope.tistory.com/236