[백준14003_자바스크립트(javascript)] - 가장 긴 증가하는 부분 수열 5

🔴 문제

가장 긴 증가하는 부분 수열 5

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const [[n], A] = fs
  .readFileSync(path)
  .toString()
  .trim()
  .split('\n')
  .map((it) => it.split(' ').map(Number));

const lis = [A[0]];
const log = [[0, A[0]]];

for (let i = 1; i < n; i++) {
  const target = A[i];

  if (lis.at(-1) < target) {
    lis.push(target);
    log.push([lis.length - 1, target]);
  } else {
    let left = 0;
    let right = lis.length - 1;

    while (left < right) {
      const mid = Math.floor((left + right) / 2);

      if (lis[mid] < target) left = mid + 1;
      else right = mid;
    }

    lis[left] = target;
    log.push([left, target]);
  }
}

console.log(lis.length);

let idx = lis.length - 1;
const result = [];

for (let i = n - 1; i >= 0; i--) {
  if (log[i][0] === idx) {
    result.push(log[i][1]);
    idx -= 1;
  }
}
console.log(...result.reverse());

🟢 풀이

⏰ 소요한 시간 : -

가장 긴 증가하는 부분 수열 2을 풀고 풀어본 문제! 사실 못풀어서 정답을 봤다.
LIS 2는 수열의 길이만 출력하면 되는데 이 문제는 수열도 같이 출력해줘야 한다.
따라서 역추적이라는 개념을 도입한다.
LIS 2와 동일하게 구현하되, lis배열에 요소를 추가하거나 요소를 바꿀때 어떤 요소를 어떤 인덱스에 넣어놨는지를 log에 기록한다.

그 후 n-1부터 0까지 가면서 lis의 마지막 요소부터 0까지 가는 log를 찾아주면 된다.
역추적 개념이 헷갈릴 수 있는데 해당 포문을 손코딩으로 한번만 돌려봐도 이해된다.

🔵 Ref

[백준12015_자바스크립트(javascript)] - 가장 긴 증가하는 부분 수열 2
[Python] 백준 14003 - 가장 긴 증가하는 부분 수열 5