[Baekjoon] 18870번 : 커트라인 문제풀이 (Node.js)

https://www.acmicpc.net/problem/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 filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
const [n, ...arr] = require('fs')
  .readFileSync(filePath)
  .toString()
  .trim()
  .split(/\s/);

const parseIntArr = arr.map(item => parseInt(item));
const set = [...new Set(parseIntArr)].sort((a, b) => a - b);
const object = {};
const compressionArr = [];

for (let i = 0; i < set.length; i++) {
  object[set[i]] = i;
}
for (let i = 0; i < n; i++) {
  compressionArr.push(object[parseIntArr[i]]);
}
console.log(compressionArr.join(' '));

풀이

1. Set을 사용하여 중복이 제거된 배열을 만들고 오름차순으로 정렬한다.
2. 중복이 제거된 배열에 반복문을 돌려서 오브젝트에 해당값을 키로, 해당값에 인덱스를 키값으로 지정한다.
3. 기존배열에 반복문을 돌려서 배열에 각요소들을 오브젝트에 키로 매핑하여찾은 키값들을 새로운 배열에 푸쉬해준다.

원래는 배열을 사용해서 풀었는데 시간초과가 나와서 오브젝트를 사용해서 풀었다.
배열을 사용하면 시간복잡도가 o(n)이지만 오브젝트를 사용하면 o(1)이 된다.