[Algorithm/JS] 백준 18870번 좌표 압축

🔗 문제 바로가기 (opens new window)

Question

수직선 위에 N개의 좌표 X1, X2, ..., XN이 있다. 이 좌표에 좌표 압축을 적용하려고 한다.

Xi를 좌표 압축한 결과 X'i의 값은 Xi > Xj를 만족하는 서로 다른 좌표의 개수와 같아야 한다.

X1, X2, ..., XN에 좌표 압축을 적용한 결과 X'1, X'2, ..., X'N를 출력해보자.

Input

첫째 줄에 N이 주어진다.

둘째 줄에는 공백 한 칸으로 구분된 X1, X2, ..., XN이 주어진다.

Output

첫째 줄에 X'1, X'2, ..., X'N 을 공백 한 칸으로 구분해서 출력한다.

Example

Input 1

5
2 4 -10 4 -9

Output 1

2 3 0 3 1

Input 2

6
1000 999 1000 999 1000 999

Output 2

1 0 1 0 1 0

Solution

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에 대입한다.