좌표 압축

알고리즘을 풀다 보면 좌표압축이라는 테크닉이 필요합니다.저는 좌표압축을 "순위가 중요한 알고리즘에서, 입력값의 갯수보다 입력값의 범위가 클 때 사용하는 방법", 이라고 생각하고 있습니다. 1차원의 좌표로 예를 들어보겠습니다.n개의 x값 을 입력 받아, 입력 중 두개의 x1,x2를 선택하여 사이에 존재하는 점의 개수를 구하는 작업이 있다고 가정합시다.x의 범위는 int형의 범위인 -2^31 ~ 2^31-1 이고 중복은 없습니다. n은 5000 이하입니다.입력은 n : 7, -2^31, -10000, 0 , -2000, 3, 6, 30000 , x1 = -10000, x2 = 30000 대략적으로 보면 그림과 같이 나타나게 됩니다. x1,x2 사이의 값을 구하게 되면 4개의 값이 나오게 됩니다. 이 경우 위..

원문링크 : 좌표 압축