백준 9251 LCS [JavaScript / Node.js]

문제

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

 

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

 

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

풀이

const fs = require("fs");

// 문제 링크 : https://www.acmicpc.net/problem/9251
// 제출 시 path : /dev/stdin

const input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");

const LCS = (str1, str2) => {
  const m = str1.length;
  const n = str2.length;

  const dp = new Array(m + 1).fill(null).map(() => new Array(n + 1).fill(0));

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

  let result = "";
  let i = m,
    j = n;

  while (i > 0 && j > 0) {
    if (str1[i - 1] === str2[j - 1]) {
      result = str1[i - 1] + result;
      i--;
      j--;
    } else if (dp[i - 1][j] > dp[i][j - 1]) {
      i--;
    } else {
      j--;
    }
  }

  return result;
}

const solution = (input) => {
  const [firstArr, secondArr] = input;
  const answer = LCS(firstArr, secondArr);
  return answer.length;
};

console.log(solution(input));

해설

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

str1 = ACAYKP

str2 = CAPCAK

dp[i][j]	j=0	j=1	j=2	j=3	j=4	j=5	j=6
i=0	0	0	0	0	0	0	0
i=1	0	0	1	1	1	1	1
i=2	0	1	1	1	2	2	2
i=3	0	1	2	2	2	3	3
i=4	0	1	2	2	2	3	3
i=5	0	1	2	2	2	3	4
i=6	0	1	2	3	3	3	4

i=0 -> j=0,1,2,3,4,5,6 다 비교. 

 

dp[1][1]:

ACAYKP 과 CAPCAK 비교

A !== C 이므로 

dp[1][1]은dp[0][1]과 dp[1][0] 중 최댓값 

dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]) 

 

dp[1][2]:

ACAYKP 과 CAPCAK 비교

A === A 이므로 

dp[1][2]은 dp[0][1]+1 

dp[i][j] = dp[i - 1][j - 1] + 1;