[BOJ] 5582 - 공통 부분 문자열

✔ Problem - [5582] 공통 부분 문자열 - DP

🔰 Level

• solved.ac 기준 골드5
  

❔ How

• dynamic programming 문제이다.
• 문자열을 비교하면서, 만약 같은 문자열이 등장하면 길이를 더해줘야 한다.
• 2차원 배열을 이용해서, 문자열의 인덱스와 배열 인덱스를 이용한다.
• 같은 문자열이 나오면 해당 dp배열의 오른쪽 아래 대각선 자리에 왼쪽 위 대각선 값에 1을 더한 값을 넣어준다.
• 문자열의 최대 길이를 구해야 하므로 answer의 값을 계속 큰 값으로 갱신해줘야 한다.

✅ Source Code

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

let str1 = inputs[0];
let str2 = inputs[1];
const len1 = str1.length;
const len2 = str2.length;
let dp = Array.from(Array(len1 + 1), () => Array(len2 + 1).fill(0));
let answer = 0;

for (let i = 1; i <= len1; i++) {
    for (let j = 1; j <= len2; j++) {
        if (str1[i - 1] === str2[j - 1])
            dp[i][j] = dp[i - 1][j - 1] + 1; //대각선에 있는 값 + 1
        answer = Math.max(answer, dp[i][j]); //일치하는 문자열 최대 길이 갱신.
    }
}

console.log(answer);