백준 18353번 병사재배치 Node.js 풀이

문제 링크

- 풀이

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

const N = Number(input.shift());

const numArr = input[0].split(" ").map(Number);

numArr.reverse();

let arr = [0];

for (let x of numArr) {
  if (x > arr[arr.length - 1]) {
    arr.push(x);
  } else {
    const endIndex = findFirstGreaterOrEqualIndex(arr, x, 0, arr.length - 1);

    arr[endIndex] = x;
  }
}

function findFirstGreaterOrEqualIndex(arr, target, startIndex, endIndex) {
  while (startIndex < endIndex) {
    const midIndex = Math.floor((startIndex + endIndex) / 2);

    if (arr[midIndex] >= target) {
      endIndex = midIndex;
    } else {
      startIndex = midIndex + 1;
    }
  }

  return endIndex;
}

console.log(numArr.length - arr.length + 1);

이해하는데에 시간이 오래걸렸다.

일단 reverse()를 왜 해주어야하는지부터 이해가 안갔는데, 이 문제에서는 주어진 배열 안에서 내림차순으로 배치를 해주고 싶어한다.

그렇기때문에 정렬을 해주는것이 아니고 원래 배열 상태를 유지하면서 내림차순으로 정렬을 해주고 싶어하는 것이다.

그렇기 때문에, reverse()메서드를 통해서 LIS 알고리즘 문제로 변환을 할수 있다.

LIS 알고리즘 문제는, 해당 배열에서 가장 긴 수열을 찾아주는 것이다.

예를 들어서

const arr = [1, 3, 4, 2, 6, 3];

라는 배열이 있을때, 가장 연속적으로 존재하는 수열은 [1, 3, 4]가 된다.

그렇기때문에 reverse()를 해주어서 배열을 뒤집어준다.

이제 반복문을 돌면서 만약 해당 값이 수열을 담아주기 위해 만든 배열 arr의 마지막 값보다 크다면, push를 해준다.

하지만 만약 그렇지 않다면 이진탐색을 통해서 교체해주어야할 인덱스 값을 찾아주어야한다.

만약

[0, 2, 5, 8] 까지 배열이 담아진 상태에서 4가 값으로 들어온다먼

초기의 midIndex는 1이 되고, arr[1]은 2이고 조건에 맞지 않으므로 startIndex를 midIndex + 1로 교체해준다.

그 후의 midIndex는 2가 되고 arr[2], 즉 5는 4보다 크므로 endIndex를 midIndex로 교체해주어서

5와 4를 바꿔주는것이다.

여기선 조건에 맞는 해당 인덱스에 값만 바꿔주면 되기때문에, 직접적인 수열 배열을 구하는것은 아니었다.