백준 18860번 JavaScript

첫 번째 풀이(메모리 초과 실패)

const fs = require('fs');
const input = fs.readFileSync('testFile.txt').toString().trim().split('\n');

const count = Number(input[0]);
const arr = input[1].split(' ').map(Number);
let result = '';

for(let i = 0 ; i < count ; i += 1 ){
  const countSet = new Set();
  const smallX = arr.filter(currentNum => currentNum < arr[i]);
  for(let j = 0 ; j < smallX.length ; j += 1){
    countSet.add(smallX[j]);
  }
  result += countSet.size + ' ';
}

console.log(result)

좌표가 100만개까지 주어지는 것을 간과하고 n 제곱의 시간복잡도로 풀었다가 메모리 초과가 났습니다.

좌표 압축은 수의 범위가 매우 큰 상황에서 수의 값과 상관 없이 숫자 간의 대소 관계만 알면 될 때 이용하는 알고리즘입니다. 쉽게 말해 숫자 간의 크기 순위로 변경하는 것입니다.
배열 [2, 4, -10, 4, -9]가 있을 때, 이를 순위로 표현하면 [2, 3, 0, 3, 1]이 됩니다.

1. 좌표 압축을 할 배열을 임시의 배열에 중복이 없도록 정렬합니다.
2. 오름차순으로 나열한 배열을 매핑합니다.

두 번째 풀이(정답 판정)

const fs = require('fs');
const input = fs.readFileSync('/dev/stdin').toString().trim().split('\n');

const count = Number(input[0]);
const arr = input[1].split(' ').map(Number);

//set으로 중복을 제거 후 정렬을 위해 다시 배열로 바꿈
const uniqueArr = [...new Set(arr)];
sortedArr = uniqueArr.sort((a, b) => a-b);

//오름차순으로 정렬된 배열을 그대로 매핑
const resultMap = new Map();
for(let i = 0 ; i < sortedArr.length ; i += 1){
  resultMap.set(uniqueArr[i], i)
}

let result = '';
for (n of arr){
  result += resultMap.get(n) + ' ';
}

console.log(result);