정렬 - 좌표 압축

문제 (백준 18870)

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표 Xj의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

입력

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

출력

첫째 줄에 X'1, X'2, ..., X'N을 공백 한 칸으로 구분해서 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• -109 ≤ Xi ≤ 109

예제 입력 1

5
2 4 -10 4 -9

예제 출력 1

2 3 0 3 1

예제 입력 2

6
1000 999 1000 999 1000 999

예제 출력 2

1 0 1 0 1 0

---

📝풀이 과정

좌표 압축이라는 개념에 대해 이해하고 있어야한다.

https://smhope.tistory.com/235

좌표압축

정리하자면,

0, 1, 2, 3, 100, 150 이라는 숫자가 주어졌을 때, 

3과 100같은 경우에는 4부터 99까지의 숫자를 사용하지 않음에도 탐색해야한다는 불편함이 있다.

이것을 없애고자 그냥 0, 1, 2, 3, 4, 5 이렇게 좌표를 압축해서 표현하자는 말이다.

압축해서 표현하니 오름차순 정렬 후 인덱스 값을 표현한 것과 같다.

 

예제 입력 1을 예시로 풀이과정을 적어본다.

2, 4, -10, 4, -9 를 오름차순으로 정렬한다. ➡ -10, -9, 2, 4, 4

그리고 인덱스로 표현한다. ➡ 0, 1, 2, 3, 4

중복된 숫자인 경우에는 똑같은 인덱스로 표현해야하므로 Set을 활용해 중복된 값을 제거한다.

다시 오름차순 정렬 후 인덱스로 표현하면 다음과 같다.

0, 1, 2, 3, 3

 

원본 배열에 맞춰서 정답을 리턴해야한다.

그렇기 때문에 오름차순으로 정렬한 요소에 대한 인덱스를 해쉬맵을 사용해 저장하고

원본배열을 순회하면서 해쉬맵의 값으로 변경해주면 된다.

🛠코드

let [n, coordinates] = require('fs').readFileSync(0).toString().trim().split('\n');
coordinates = coordinates.split(' ').map(Number);

function solution(coordinates) {
  const hashMap = new Map();
  const s = [...new Set(coordinates)].sort((a, b) => a - b);
  s.forEach((n, i) => hashMap.set(n, i));

  return coordinates.map((c) => hashMap.get(c)).join(' ');
}

console.log(solution(coordinates));

 

좌표 압축이라는 개념을 이해하는 것에 어려움을 느꼈다. 코드로 구현하는 과정은 그리 까다롭지 않았다.