좌표 압축 알고리즘 이란?

백준 18870번 좌표압축문제를 풀려고 하다가, 일단 좌표압축의 개념부터 알아야 할 것 같아서 정리해본다. 좌표 압축 알고리즘이란? : 모든 구간이 아니라, 중요한 구간이나, 숫자만 들고있는 기법. → 순위가 중요한 알고리즘에서 입력값의 개수 < 입력값의 범위일때 사용한다. 값보다 값의 순위가 중요하기 때문에, 값을 임의의 값으로 변경하되 순위만 유지하여도 문제를 풀 수 있도록 만드는 것이다. 예시로는 카카오 코드 페스티벌 5번 캠핑 문제가 있는데, 이 경우 좌표 x,y의 범위는 0 ~ 2^31-1 이지만, 입력받는 좌표의 개수는 최대 5000개이다. 만약 입력의 좌표를 그대로 반영하여 문제를 푼다고 하면 배열의 크기가 2^31-1 개가 되어야하며, 2차원이기 때문에 탐색에 너무 많은 시간이 들게 된다...