[boj] 18870. 좌표 압축 (node.js)

문제 요약

[boj] 18870. 좌표 압축 (node.js)

• 문제에서 주어진 좌표의 순서대로, 각 좌표마다 계산 결과를 출력하는 문제
• 계산할 것: 해당 수보다 작은 수 (중복되지 않는)의 개수!

풀이

• 문제에서 중복되지 않으며 해당 수보다 작은 수의 개수를 구하라고 했으므로! 중복 제거와 정렬시킨 상태에서 해당 수의 인덱스를 세면 된다.

풀이 01: 단순한 풀이 (값 정렬, 인덱스 정렬)

const solution = () => {
  const N = Number(input());
  let rank = 0;
  let prevIdx = 0;
  let arr = input()
    .split(" ")
    .map((elem, idx) => [idx, Number(elem)])
    .sort((a, b) => a[1] - b[1]);
  let result = arr
    .map((elem, idx) => {
      if (elem[1] == arr[prevIdx][1]) return [...elem, rank];
      rank++;
      prevIdx = idx;
      return [...elem, rank];
    })
    .sort((a, b) => a[0] - b[0])
    .map((elem) => elem[2]);
  console.log(result.join(" "));
};

1. 깂이 입력된 순서(index)를 배열에 저장해 두고,
2. 좌표 값을 기준으로 정렬한다.
3. 정렬 완료된 상태이므로 반복문을 사용해 rank를 매긴다. 이때 이전 값과 현재 값을 비교하여 중복되는 값일 경우 동일한 rank를 할당한다.

풀이 02: 개선한 풀이 (정렬, 이분탐색)

const solution = () => {
  const N = Number(input());
  let initArr = input().split(" ").map(Number);
  let rank = {};
  let results = [];
  let arr = Array.from(new Set([...initArr].sort((a, b) => a - b)));
  arr.forEach((value) => {
    rank[value] = binarySearch(0, arr.length, value);
  });
  initArr.forEach((value) => results.push(rank[value]));
  console.log(results.join(" "));

  function binarySearch(L, R, X) {
    let result = R;
    while (L <= R) {
      let mid = Math.floor((L + R) / 2);
      if (arr[mid] < X) {
        L = mid + 1;
      } else {
        result = mid;
        R = mid - 1;
      }
    }
    return result;
  }
};

• 정렬이 완료된 상태에서 이분탐색을 수행한다. 특정 좌표를 대상으로 이분탐색을 수행하여, 해당 좌표 보다 작은 좌표의 개수를 알아낼 수 있다.
• new Set()를 이용한 중복제거로 코드를 더 단순화했다. Set 객체 또한 forEach() 메서드를 쓸 수 있다. forEach((value, key, set) => { /* ... */ } )

주절주절

• 반성하자면, 이 문제의 경우 일단 정렬 문제이며 정렬이 끝나고 탐색이 필요하기 때문에! 정렬 이후의 탐색에서 이분탐색을 고민해봤어야 했다. 집합으로 만들어서 중복 제거한 상태에서 이분탐색을 하면 딱! 깔끔히 풀리는 문제였다.
• 처음 풀이가 로직상으로는 더 깔끔하다. 처음에 떠올릴 수 있던 풀이었고, 응용 없이도 깔끔히 풀릴 수 있는 문제였다. 그래도 맞았지만 넘어가지 않고 다른 사람의 코드를 찾아보고 공부해 보니, 이분 탐색을 활용 가능한 경우였음에도 놓쳤다는 걸 알았고 더 보충할 수 있었다. ^-^

전체 코드

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  const N = Number(input());
  let initArr = input().split(" ").map(Number);
  let rank = {};
  let results = [];
  let arr = Array.from(new Set([...initArr].sort((a, b) => a - b)));
  arr.forEach((value) => {
    rank[value] = binarySearch(0, arr.length, value);
  });
  initArr.forEach((value) => results.push(rank[value]));
  console.log(results.join(" "));

  function binarySearch(L, R, X) {
    let result = R;
    while (L <= R) {
      let mid = Math.floor((L + R) / 2);
      if (arr[mid] < X) {
        L = mid + 1;
      } else {
        result = mid;
        R = mid - 1;
      }
    }
    return result;
  }
};

let _line = 0;
const input = () => stdin[_line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});