[BOJ 5582] 공통 부분 문자열

문제

 

5582번: 공통 부분 문자열

 

예시 코드

function solution() {
  const str1 = input();
  const str2 = input();
  const len1 = str1.length;
  const len2 = str2.length;
  const dp = Array.from(Array(len1 + 1), () => Array(len2 + 1).fill(0));
  let maxLen = 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;
        maxLen = Math.max(maxLen, dp[i][j]);
      }
    }
  }

  return maxLen;
}

 

풀이

두 문자열에서 LCS(Longest Common Substring, 가장 긴 공통부분 문자열)을 찾는 문제입니다.

 

DP를 이용해서 풀 수 있습니다.

 

두 문자열을 한 문자씩 비교하면서, 같은 문자가 나타나면 이전에 비교한 문자들의 연속성을 이어갑니다. 이를 위해 2차원 배열 dp를 사용하여, 같은 문자가 나타날 때마다 이전 위치의 값(dp[i-1][j-1])에 1을 더합니다.

 

dp[i][j]는 '첫 번째 문자열의 i번째 문자와 두 번째 문자열의 j번째 문자가 같을 때, 그 두 문자까지의 가장 긴 공통부분 문자열의 길이'를 의미합니다.

 

dp 배열은 (첫 번째 문자열의 길이 + 1) * (두 번째 문자열의 길이 + 1)이며, 모든 값을 0으로 초기화 해줍니다.

 

e.g.

str1 = 'ABCD'

str2 = 'BCDE'인 경우

dp 배열은 다음과 같습니다.

 

0	0	0	0	0
0	0	0	0	0
0	1	0	0	0
0	0	2	0	0
0	0	0	3	0

 

str1의 2번 문자와 str2의 1번 문자가 'B'로 같으므로 dp[2][1] = dp[1][0] + 1 = 1입니다.

str1의 3번 문자와 str2의 2번 문자가 'C'로 같으므로 dp[3][2] = dp[2][1] + 1 = 2입니다.

str1의 4번 문자와 str2의 3번 문자가 'D'로 같으므로 dp[4][3] = dp[3][2] + 1 = 3입니다.

 

따라서 답은 3이 됩니다.