[백준18870_자바스크립트(javascript)] - 좌표 압축

🔴 문제

좌표 압축

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], inputs] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));
const numbers = Array.from(new Set(inputs)).sort((a, b) => a - b);
const map = new Map();

for (let i = 0; i < numbers.length; i++) {
  map[numbers[i]] = i;
}

let ans = '';
for (const input of inputs) {
  ans += map[input] + ' ';
}

console.log(ans.trim());

🟢 풀이

⏰ 소요한 시간 : -

N개의 수 중에서 자기보다 작은 수가 몇 번 나왔는지 구하는 구현문제.

N의 범위가 1,000,000이므로 N번 반복하면서 매번 indexOf와 같은 O(n)의 시간복잡도가 드는 메서드를 사용하면 시간초과가 발생할 것이다.

그래서 N개의 숫자를 중복을 제거/정렬한 후 한번만 순회하면서 map에 등장한 순서를 넣어준다.
이때 key-value는 각각 등장한 숫자 - 나타난 인덱스로 매핑해준다.

그 후 input을 다시 순회하며 등장한 인덱스를 map에서 찾아주면 된다.

🔵 Ref