문제

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

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

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

1 ≤ N ≤ 1,000,000
-10^9 ≤ Xi ≤ 10^9

입력

첫째 줄에 N이 주어진다.

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

출력

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

예제 입력

5
2 4 -10 4 -9

예제 출력

2 3 0 3 1

내가 했던 풀이 방법

1. X의 값을 그대로 가진 Set을 만들어 중복을 제거해준다. (sort 연산 횟수를 줄이기 위함)
2. Set을 배열로 다시 변환하고 오름차순으로 정렬해준다.
3. Map에 정렬된 배열의 요소를 key로 하고 index를 value로 하여 추가해준다.
4. X의 요소를 순차적으로 접근하고 해당 요소를 key로 하는 value를 answer에 더해준다.

코드

const fs = require('fs');
let [N, X] = fs.readFileSync(0, 'utf-8').toString().trim().split('\n');

N = Number(N);
X = X.trim().split(' ').map(Number);

let sorted = Array.from(new Set(X.slice(0))).sort((a, b) => a - b);

let map = new Map();
for (let i = 0; i < sorted.length; i++) {
  map.set(sorted[i], i);
}

let answer = '';
for (let i = 0; i < N; i++) {
  answer += map.get(X[i]) + ' ';
}

console.log(answer.trim());

회고

생각보다 쉽게 풀이 가능했다. 시간초과가 정말 많이 나는 문제인 것 같길래 sort에서 시간초과 나겠지...? 라는 마음으로 제출했는데 한 번에 통과해서 당황