[JavaScript] 백준 골드 5 : 5582 - 공통 부분 문자열

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

5582번: 공통 부분 문자열

---

📌 작성한 코드 

// 5582
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Gold/test.txt";
let input = fs.readFileSync(filePath).toString().trim().split("\n");

const first = input[0];
const second = input[1];

const dp = Array.from({ length: first.length + 1 }, () => new Array(second.length + 1).fill(0));
let max = 0;

for (let i = 1; i <= first.length; i++) {
    for (let j = 1; j <= second.length; j++) {
        if (first[i - 1] === second[j - 1]) {
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        if (dp[i][j] > max) max = dp[i][j];
    }
}

console.log(max);

 

📌 설명 

공통 부분 문자열을 어떻게 구하는지에 대해 이미지와 표로 너무 멋지게 설명해놓은 블로그가 있어서 소개하려고 한다.

https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence#longest-common-subsequence-substring

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

해당 블로그를 통해 어떻게 점화식을 세우고 구하는지 충분히 이해할 수 있을 것이다. 

 

📍 주의해야 하는 부분 

dp를 채워나갈때 인덱스가 0인 부분(마진)은 dp[i-1][j-1]에서 접근하기 위해서 있는 부분이라 0으로 초기화 되어있어야한다.

따라서, dp를 선언할 때 0을 할당하고, 반복문 인덱스를 돌 때 1부터 시작하되, 문자열에 접근할 때는 첫번째 문자가 0번 인덱스에 저장되어 있으니 i-1,j-1 해서 접근해야 한다. 

 

예를 들어 문자열이 ''abc', 'abd'라면 dp[1][1]에는 각각 첫번째 문자까지 비교하였을 때 최장 공통 문자열의 길이가 저장되어야 한다.

그러면 우리는 a가 같으니까 1을 저장해야 함을 알 수 있다.

- 반복문 i, j : (1, 1) -> (i, j)로 접근

- 이때 각 문자열에 접근할 때 사용하는 인덱스 : 0 -> (i-1, j-1)로 접근

- 저장되는 위치 : (1, 1) -> (i, j)로 접근

const first = input[0];
const second = input[1];

const dp = Array.from({ length: first.length + 1 }, () => new Array(second.length + 1).fill(0));
let max = 0;

for (let i = 1; i <= first.length; i++) { // dp는 1에서 시작
    for (let j = 1; j <= second.length; j++) {
        if (first[i - 1] === second[j - 1]) { // -1한 위치로 접근 (문자열은 0에서 시작)
            dp[i][j] = dp[i - 1][j - 1] + 1;
        }
        if (dp[i][j] > max) max = dp[i][j];
    }
}

 

✅ 성공