백준 18353번 JavaScript

백준18353번 node.js

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

const n = Number(input[0]);
let arr = input[1].split(" ").map(Number);

function lowerBound(arr, start, end, target) {
  let result = 0;
  while (start < end) {
    let mid = parseInt((start + end) / 2);
    if (target <= arr[mid]) {
      end = mid;
    } else {
      start = mid + 1;
    }
  }
  return end;
}

//증가하는 부분수열을 구하기 위해 뒤집어줍니다
arr.reverse();

let newArr = [0];
for (let i = 0; i < n; i += 1) {
  if (newArr[newArr.length - 1] < arr[i]) {
    newArr.push(arr[i]);
  } else {
    let result = lowerBound(newArr, 0, newArr.length, arr[i]);
    newArr[result] = arr[i];
  }
}

//newArr의 0은 비교하기 위해 넣은 임의의 값이므로 제외
console.log(n - (newArr.length - 1));

가장 긴 증가하는 부분 수열을 구하는 문제였습니다.
LIS(Longest Increasing Subsequence) 알고리즘입니다.

부분 수열은 어떤 수열이 주어질 때, 그 수열에서 일부 원소를 뽑아내어 새로 만든 수열입니다.
이 수열이 오름차순을 유지하면 증가하는 부분 수열이 됩니다.

위의 수열에서 증가하는 부분 수열은 다양합니다.
[2, 5], [2, 6], [2, 7], [2, 3, 6], [5, 6], [3, 6, 7, 9],...

가장 긴 수열은

[3, 5, 6, 7, 9], [2, 5, 6, 7, 9] 이렇게 두 가지네요!
LIS는 반드시 답이 하나로 결정되는 것이 아닙니다.
문제에서도 답의 LIS의 길이를 출력하도록 하거나, 수열을 구한다면 답이 여러 개가 출제된다고 합니다.

해당 문제는 길이를 구하는 문제로, 이진 탐색을 이용하여 O(NlogN)의 시간복잡도로 풀이할 수 있고, 실제로 길이만 구할 수 있는 풀이법입니다.

//부분 수열을 만들 newArr을 주어진 수열의 인덱스를 비교하기 위해 0으로 초기화해주었습니다.
let newArr = [0];
for (let i = 0; i < n; i += 1) {
  if (newArr[newArr.length - 1] < arr[i]) { 
    newArr.push(arr[i]);
  } else {
    //부분수열의 마지막 값보다 작은 경우, lowerBound로 수열에 들어갈 위치 찾아 대체해줍니다.
    let result = lowerBound(newArr, 0, newArr.length, arr[i]);
    newArr[result] = arr[i];
  }
}