[백준] 5582 공통 부분 문자열 - javascript

📌 문제

https://www.acmicpc.net/problem/5582

📌 풀이

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

let str1 = input[0].trim();
let str2 = input[1].trim();
let dp = new Array(str1.length + 1);
for (let i = 0; i < dp.length; i++) {
  dp[i] = new Array(str2.length + 1).fill(0);
}
let ans = 0;
for (let i = 1; i <= str1.length; i++) {
  for (let j = 1; j <= str2.length; j++) {
    if (str1[i - 1] === str2[j - 1]) {
      dp[i][j] = dp[i - 1][j - 1] + 1;
    } else {
      dp[i][j] = 0;
    }
    if (dp[i][j] > ans) ans = dp[i][j];
  }
}
console.log(ans);

✔ 알고리즘 : DP

✔ 배열을 만들어서 모든 값을 0으로 초기화한다.

✔ 기존의 공통 문자열 문제에서는 연속된 이라는 조건이 없었기 때문에 max메서드를 통해 계속 갱신했어야 했다.

✔ 이 문제는 연속된 공통 문자열이므로 문자열 두개를 비교하여 같다면 왼쪽위 대각선의 배열값에 +1을 해준다

✔ 문자열 두개를 비교하여 같지 않다면 현재의 dp값은 0이다.

✔ ans와 비교하여 최댓값을 계속 갱신한다.

✔ 난이도 : 백준 기준 골드 5