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

🔴 문제

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

🟡 Sol

const fs = require('fs');
const path = process.platform === 'linux' ? '/dev/stdin' : 'input.txt';
const inputs = fs.readFileSync(path).toString().trim().split('\n');

const n = Number(inputs[0]);
const A = [0, ...inputs[1].split(' ').map(Number)];
const dp = Array.from({ length: n + 1 }, () => [0, []]);

for (let i = 1; i <= n; i++) {
  for (let j = 0; j < i; j++) {
    if (A[i] > A[j] && dp[j][0] + 1 > dp[i][0]) {
      dp[i][0] = dp[j][0] + 1;
      dp[i][1] = [...dp[j][1], A[i]];
    }
  }
}

let ansIdx = 0;
for (let i = 1; i <= n; i++) {
  if (dp[ansIdx][0] < dp[i][0]) ansIdx = i;
}

console.log(dp[ansIdx][0]);
console.log(...dp[ansIdx][1]);

🟢 풀이

⏰ 소요한 시간 : -

가장 긴 증가하는 부분 수열 LIS 문제유형이다.
이 문제는 가장 긴 증가하는 부분 수열의 길이만 출력하는 것이 아니라 수열도 출력해줘야 하기 때문에 dp를 3차원 배열로 만들어 줬다.
즉 dp[i]는 i번째 수를 마지막으로 하는 가장 긴 증가하는 부분 수열이고, dp[i]에는 2칸짜리 배열을 넣어줬다. dp[i]의 0번째 요소에는 가장 긴 증가하는 부분 수열의 길이, 1번째 요소에는 부분 수열을 배열로 넣어주었다.

이런 방법을 사용하니 정답은 나왔지만 아래처럼 다른분의 코드의 메모리와 시간복잡도가 엄청 차이나버렸다..

ㅜ.. 그래서 코드를 참고했는데 대충 이분탐색을 사용하시던데 아예 모르겠다..
나중에 더 성장하면 다시 봐야겠다

🔵 Ref