[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);
Author And Source
이 문제에 관하여([BOJ] 5582 - 공통 부분 문자열), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@songjy377/BOJ-5582-공통-부분-문자열저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)