좌표 압축

문제

https://www.acmicpc.net/problem/18870

정답

첫 번째 시도에서 시간초과가 발생했다. 원인을 분석하니 Array.map()에서 indexof()를 사용하는 과정에서 최악의 경우 O(n^2)의 시간 복잡도가 발생하여 생긴 문제였다.

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

const resultList = list.split(" ").map((item) => +item);

const sortList = Array.from(new Set(resultList)).sort((a, b) => a - b);

console.log(
  resultList
    // O(N^2)의 시간 복잡도가 발생할 수 있음.
    .map((item) => {
      return sortList.indexOf(item);
    })
    .join(" ")
);

따라서 indexOf()를 사용하는 대신 Map를 사용하여 풀이하도록 하였다.

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

// 리스트 변환하기
const resultList = list.split(" ").map(Number);

// 중복된 값 제거 후에 정렬하기
const sortList = Array.from(new Set(resultList)).sort((a, b) => a - b);

const map = new Map();

// 정렬한 값 등록하기
sortList.forEach((item, index) => {
  map.set(item, index);
}); // Map(2) { 999 => 0, 1000 => 1 }

let answer = "";
resultList.forEach((item) => {
  answer += map.get(item) + " ";
});

console.log(answer);

map를 사용하는 이유는 map.get()의 경우 키를 해시값으로 갖기 때문에 O(1)의 시간 복잡도를 갖기 때문이다. 따라서 훨씬 효율적으로 문제를 풀이할 수 있다.