백준[node.js] > 9251번 LCS

문제

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

내풀이

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

이 문제는 유명한 문제라고 하는데 처음에 어떻게 접근할 지 몰라 다른사람들의 풀이를 참고하였다.

간단하게 

ACAYKP
CAPCAK

두문자의 LCS를 찾으려면 아래와 같은 2 차원 배열을 만들고 채워서 가장 큰 수를 확인하면 된다. 

 

     A  C  A  Y  K  P     

C   

A   

P   

C   

A  

K   

 

이렇게 2차원 배열을 만들고 채우면 된다. 

위 2차원배열을 dp라고 칭하면 dp[0][3] 은 문자열 C와 문자열 ACAY 의 LCS길이로 채워진다. 

dp[1][3]은 문자열 CA와 문자열 ACAY의 LCS의 길이다

 

문자열 CA와 문자열 ACAY의 LCS의 길이를 알고 싶으면

CA와 ACA 의 LCS의 길이

C와 ACAY의 LCS의 길이

의 길이중 더 큰 숫자를 택하면 된다. 

 

그런데  CAPCAK 와 ACAYK의 LCS의 길이를 알고 싶으면

CAPCA 와 ACAY 의 LCS의 길이 + 1 을 면 된다. 

왜냐하면 마지막 K로 같기 때문이다

 

코드를 보면서 차근차근 이해하면 순간 이해가 될것이다.

 

 

let fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().trim();

let [strA, strB] = input.split("\n");

let dp = Array.from({ length: strA.length + 1 }, () => {
    return Array(strB.length + 1).fill(0);
});

for (let row = 1; row <= strA.length; ++row) {
    for (let col = 1; col <= strB.length; ++col) {
        if (strA[row - 1] === strB[col - 1]) {
            dp[row][col] = dp[row - 1][col - 1] + 1;
        } else {
            dp[row][col] = Math.max(dp[row][col - 1], dp[row - 1][col]);
        }
    }
}

console.log(dp[strA.length][strB.length]);