18870 좌표압축 NodeJS 좌표압축이 뭔지 시간 메모리 관리까지

이번 문제는 처음 보는 좌표압축이라는 개념과 메모리, 시간초과로 애좀 먹고 한 단계 발전하게 된 문제다. 문제를 풀기위해서 좌표압축이 무엇인지 알아채야한다. 처음 문제를 보고 Xi > Xj면 Xj 범위가 너무 넓은거 아닌가 생각했는데 주어진 배열에서 대소 비교만 하면 되는 것이었다. 중복값에 대한 처리도 필요한데 조건에 서로다른 Xj라고 명시되어 있기 때문이다.
이 두가지를 합쳐 생각해보면 1. 중복제거된 2. 오름차순 정렬된 배열을 만들어 이를 활용하면 된다. 새로 만든 배열과 그 요소의 인덱스를 문제 해결에 사용하는 방식이다. 예제를 통해 나온 배열을 만들어보면 [-10, -9, 2, 4]이다. 이보다 작은 수가 없는 -10은 인덱스가 0이다. 자신보다 작은 수가 한 개인 -9의 인덱스는 1이다. 이렇게 그 수의 압축된 좌표값을 얻는 방식이다.

접근방식

1. 중복제거하고 오름차순 정렬된 배열 생성
2. input값의 순서대로 그 값의 좌표압축 값을 새로 생성한 배열에서 가져옴

문제

1-1 위 방식을 안쓰고 그냥 하면 메모리 초과

//
const [N, coordinatesString] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const result = coordinates.split(" ").map((coordinate, idx, arr) => {
  const X = arr.filter((item) => item < coordinate);
  return [...new Set(X)].length ?? 0;
});

맨처음 있는 그대로 풀었다. 매번 더 작은 값을 찾아서 새롭게 배열을 만들어줬는데 메모리 초과가 발생했다. 메모리 개념이 잘 잡혀있지 않기도 하지만 슬슬 효율을 생각하지 않으면 안되는 문제들이 많이 생긴다. map과 그 아래에 filter로 값을 순회하는게 N^2 으로 시간이 걸릴거같다 잘모름 또 리턴값에 Set으로 중복없애고 다시 배열로 만드는 과정까지 있어서 메모리 초과가 난 것.

2-1 인덱스 값을 그때마다 찾으면 시간 초과

const result = coordinates.map((coor) => {
  const idx = newCoorArray.indexOf(coor);
  return idx;
});

이렇게 인덱스를 가져오는 방식을 써봤더니 시간초과가 났다. 아무래도 map으로 순회도 하고 indexOf가 앞에서부터 일치하는 값까지 찾다보니 시간이 오래 걸린다고 하더라. 그럼 이걸 어떻게 해야 시간이 단축되나 찾아보니까 forEach로 순회해서 Object를 쓰거나 Map을 써서 인덱스 값을 저장하면 빠르다고 한다. 얘네들을 쓰면 인덱스로 값을 찾는 접근은 빠른데 forEach를 쓰면 순회하는건 똑같은거 아닌가 생각은 든다. 하지만 빠르니까 뭐.

정답

Map말고 Object도 사용가능.

const fs = require("fs");
const filePath = process.platform === "linux" ? "dev/stdin" : "input.txt";
const [N, coordinatesString] = fs
  .readFileSync(filePath)
  .toString()
  .trim()
  .split("\n");

const map = new Map();
const coordinates = coordinatesString.split(" ").map(Number);
const newCoorArray = [...new Set(coordinates)].sort((a, b) => a - b);
newCoorArray.forEach((value, index) => {
  map.set(value, index);
});
const result = coordinates.map((coor) => {
  return map.get(coor);
});
console.log(result.join(" "));