[백준] 18870

좌표 압축

문제

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

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

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

입력

첫째 줄에 N이 주어진다.

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

출력

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

풀이

const coordPress = () => {
  let input = require("fs")
    .readFileSync("/dev/stdin")
    .toString()
    .trim()
    .split("\n")
    .map((n) => n.split(" ").map(Number));
  const arr = [...new Set(input[1])].sort((a, b) => a - b);
  let obj = {};
  let ans = [];
  arr.forEach((val, idx) => (obj[val] = idx));
  for (let i of input[1]) {
    ans.push(obj[i]);
  }
  console.log(ans.join(" "));
};

coordPress();

반성회

배열을 탐색할 땐 시간복잡도가 O(n) 이 드므로 배열 대신 객체 (JS), 사전 (Python), 해시테이블 등을 사용하여 인덱스를 가져올 때 접근 시간복잡도가 O(1) 이 되게 한다