18870 좌표 압축

Solution1 (시간초과)

const fs = require('fs');
const [N, ...input] = fs
  .readFileSync('dev/stdin')
  .toString()
  .trim()
  .split(/\s+/)
  .map(Number);

const counts = [];
input.map((num, idx) => {
  let count = 0;
  const coords = [];
  for (let i = 0; i < N; i++) {
    if (i === idx) continue; // (1)
    if (num > input[i] && !coords.includes(input[i])) {
      // (2)
      coords.push(input[i]);
      count++;
    }
  }
  counts.push(count); // (3)
});

console.log(counts.join(' '));

/\s+/ 는 모든 공백을 제거하는 정규식이다.

map과 반복문을 사용해 Xi > Xj 를 만족하는 좌표의 개수를 찾는다.

1. map 을 통해 순환하면서 순환하고 있는 인덱스와 input 의 인덱스가 같다면 해당 인덱스는 검사하지 않고 다음 반복문을 실행한다.
2. num 보다 작으면서 coord 배열에 포함되어 있지 않다면 coords 배열에 추가하고, 카운팅한다. coords 배열은 중복 검사를 방지하기 위한 배열이다.
3. 각 좌표의 Xi > Xj 를 만족하는 좌표의 개수를 counts 배열에 push 한다.

결과는 시간초과다.

Solution2 (성공)

const fs = require('fs');
const [N, ...input] = fs
  .readFileSync('dev/stdin')
  .toString()
  .trim()
  .split(/\s+/)
  .map(Number);

const set = new Set(input); // (1)
const sort = [...set].sort((a, b) => a - b); // (2)

let dic = {}; // (3)
sort.forEach((e, idx) => (dic[e] = idx)); // (4)

let result = '';
input.map((num) => (result += `${dic[num]} `)); // (5)
console.log(result);

1. 입력값의 중복 값을 제거한다. Set 은 중복값을 제거한 객체(Object)를 반환한다.
2. 중복을 제거한 set 객체를 오름차순 정렬한다. 오름차순으로 정렬하는 sort 메소드는 배열 메소드이기 때문에 spread 연산자를 사용한다.
3. dic 는 키-값 쌍을 이루는 객체타입 변수로 키(key)는 각 X 좌표를, 값(value)는 Xi > Xj 만족하는 좌표 개수를 갖는다. 2번에서 오름차순 정렬하면서 각 x 좌표의 인덱스가 조건을 만족하는 좌표의 개수가 된다.
4. 3번의 키와 값을 dic 변수에 할당한다.
5. input 을 map을 통해 반복해 dic 객체에서 해당하는 키(key)를 찾아 result에 대입한다.