문제 개요

문제: LCS

분류: DP, 문자열

난이도: 골드5

문제 풀이

• dp[i][j] : 문자열1의 i번째 인덱스까지의 문자열과 문자열2의 j번째 인덱스까지의 문자열의 LCS의 길이

두 문자열에 대해 한 글자씩 비교하며 dp 배열에 현재까지 비교한 문자열에 대한 LCS의 길이를 저장한다.

문자열 str1과 str2를 입력 받았을 때 아래를 수행한다.

1. str1[i]와 str2[j]가 같다면 dp[i-1][j-1]에 1을 더한 값을 dp[i][j]에 대입한다.
2. str1[i]와 str2[j]가 다르다면 위쪽 dp[i-1][j]와 왼쪽 dp[i][j-1] 중 더 큰 값을 dp[i][j]에 대입한다.

1번에서 dp[i-1][j-1]은 이번 문자를 포함하기 이전 문자열끼리의 LCS의 길이였기 때문에 해당 길이에서 1을 더한 값이 현재의 LCS의 길이가 된다.

모든 문자열에 대한 비교가 끝나면 dp 배열의 마지막 행 마지막 열에 있는 값이 정답이 된다.

코드

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "input.txt";
const [str1, str2] = fs.readFileSync(filePath).toString().trim().split("\n");

let dp = Array.from({ length: str1.length + 1 }, () =>
  new Array(str2.length + 1).fill(0)
);

let len1 = str1.length;
let len2 = str2.length;

for (let i = 1; i <= len1; i++) {
  for (let j = 1; j <= len2; j++) {
    dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
    if (str1[i - 1] === str2[j - 1]) {
      dp[i][j] = Math.max(dp[i - 1][j - 1] + 1, dp[i][j]);
    }
  }
}

console.log(dp[len1][len2]);