[백준] 5582 공통 부분 문자열 (Javascript)

문제

BOJ5582_공통 부분 문자열

풀이

요구사항

최장 공통 부분 문자열의 길이를 알아내는 문제

해결방안

첫 번째(그리디, 시간초과)

처음엔 아래 코드처럼 2중 for문을 돌면서 만약 동일한 문자를 만났다면 재귀함수를 호출해서 한 칸씩 앞으로 이동시켜서 답을 구하려고 했다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [str1, str2] = require('fs').readFileSync(filePath).toString().trim().split('\n');
let answer = 0;

function recursion(i, j, str) {
    if (str1[i] === str2[j]) {
        recursion(i + 1, j + 1, str + str1[i]);
    } else {
        answer = str.length > answer ? str.length : answer;
    }
}

for (let i = 0; i < str1.length; i++) {
    for (let j = 0; j < str2.length; j++) {
        if (str1[i] === str2[j]) {
            recursion(i, j, '');
        }
    }
}

console.log(answer);

하지만 이렇게 작성했더니 시간초과가 나왔다.
왜 시간초과일까 생각해봤는데, 2중 for문 안에서 재귀함수를 호출하기 때문에 시간복잡도가 $O(N^3)$이 돼서 시간초과가 나온 것 같다.

두 번째(DP, 통과)

결국 답을 찾아봤다.
이 문제는 LCS(Longest Common Substring, 최장 공통 부분 문자열)라는 알고리즘을 이용해서 풀 수 있었다.

LCS알고리즘이란 두 문자열을 2차원 배열의 행과 열로 매칭시켜 공통되는 부분 문자열의 길이를 배열의 값으로 저장하는 DP유형의 알고리즘이다.

자세한 내용은 이 블로그에 설명되어 있다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [str1, str2] = require('fs').readFileSync(filePath).toString().trim().split('\n');
const LCS = Array.from({ length: str1.length + 1 }, () => Array(str2.length + 1).fill(0));
let answer = 0;

for (let i = 0; i < str1.length; i++) {
    for (let j = 0; j < str2.length; j++) {
        if (str1[i] === str2[j]) LCS[i + 1][j + 1] = LCS[i][j] + 1;
        answer = LCS[i + 1][j + 1] > answer ? LCS[i + 1][j + 1] : answer;
    }
}

console.log(answer);

세 번째(DP, 메모리/시간 개선)

두 번째 방법은 통과되긴 하지만 2차원 배열을 사용하기 때문에 메모리와 수행시간이 낭비된다.

만약 문자열의 길이가 아니라 문자열을 출력하라고 했으면 2차원 배열에 저장된 값이 중요하기 때문에 어쩔수 없이 2차원 배열을 사용해야 하지만, 지금은 최대 길이만 구하면 되기 때문에 2차원 배열을 1차원 배열로 줄일 수 있다.

따라서 아래와 같이 기존의 2차원 LCS배열을 입력으로 들어온 두 문자열 중 하나의 길이 만큼의 크기를 가진 1차원 배열로 만들고, 나머지 하나의 문자열의 문자를 하나씩 뽑아서 비교하는 방식으로 해줌으로써 시간과 메모리를 절약할 수 있다.

const filePath = process.platform === 'linux' ? '/dev/stdin' : './Javascript/input.txt';
const [str1, str2] = require('fs').readFileSync(filePath).toString().trim().split('\n');
str1.trimEnd(); // '\r' 제거 (안 해도 상관없다)
let answer = 0;

const dp = Array(str1.length).fill(0);
for (let i = 0; i < str2.length; i++) {
    for (let j = str1.length - 1; j >= 0; j--) {
        if (str2[i] === str1[j]) {
          // j가 0일 때는 j-1이 없으므로 1을 삽입한다. 
            if (j === 0) dp[j] = 1;
            else dp[j] = dp[j - 1] + 1;
            answer = dp[j] > answer ? dp[j] : answer;
        } else dp[j] = 0;
    }
}

console.log(answer);

참고 한 코드