백준 18770 JS

문제 링크

좌표 압축

해결과정

const fs = require("fs");
let [num, ...input] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
// 배열로 추출
let arr = input[0].split(" ");
// 정답 배열
let ans = [];
// 배열 내 문자열 -> 넘버
arr = arr.map(Number);
// 중복 제거
let arr2 = new Set(arr);
// 중복 제거 후 정렬
let sortedArr = [...arr2];
sortedArr = sortedArr.sort();
// 정렬된 배열의 인덱스를 찾아 정답 배열에 push
for (let i of arr) {
  ans.push(sortedArr.indexOf(i))
}
// 정답 요구사항대로 출력
console.log(ans.join(" "));

처음 생각했던 것은 제일 작은 순으로 정렬해서 인덱스를 찾아 답을 제출하면 되겠다는 생각을 했다.

아쉽게도 시간초과가 나왔음.

배열에서의 탐색은 O(N)이라 매번 답을 찾는 과정이 오래걸린듯 하다.

객체에서는 탐색이 O(1)의 복잡도를 갖기 때문에 객체로 교체하였다.

최종

const fs = require("fs");
let [num, ...input] = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

// 입력 값 number로 바꾸기
let arr = input[0].split(" ").map(Number);
// 중복 제거
let uniqueArr = [...new Set(arr)];

// 중복 제거한 배열 정렬
let sortArr = uniqueArr.sort((a, b) => a - b);

// 정렬된 배열 map으로 만들기.
let sortMap = new Map();

// map에 값 입력 -> [가장 작은 값, 인덱스]
for (let i = 0; i < sortArr.length; i++) {
  sortMap.set(sortArr[i], i);
}

// map에서 해당 값 가져오기.
let ans = "";
for (let i of arr) {
  ans += sortMap.get(i) + " ";
}

// 결과 출력
console.log(ans);

성공~