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

공통 부분 문자열

📚 문제 설명

---

두개의 문자열이 주어졌을 때, 가장 큰 길이의 공통 부분 문자열을 찾는 문제이다.
예를 들어서 설명하는게 이해가 더 빠를 것이다.

문자열1 : ABRACADABRA
문자열2 : ECADADABRBCRDARA

공통 부분 문자열 : CA, CADA, ADABR, 빈 문자열
최장 공통 부분 문자열 : ADABR

👨🏻‍💻 풀이 과정

---

이 문제는 일전에 풀었던 백준 9251 LCS 문제와 같은 알고리즘의 더 기본적인 원리를 이용하여 풀면 되는 문제이다.

전에 설명했던 LCS 알고리즘에서 어려웠던 부분은 두 문자가 일치하지 않는 부분에는 Math.max() 를 이용하여 최장 공통 부분 수열을 저장해 나가는 부분이었다.
그러나 이번 문제에서는 연속되는 부분 문자 중 가장 긴 부분 문자를 찾으면 된다.

따라서 2차원 배열을 다음과 같이 만들어 주고 값을 채워 나가면 될 것이다.
(문자열이 "ABCD", "ABWER" 일 경우를 예시로)

	0	A	B	C	D
0	0	0	0	0	0
A	0	0	0	0	0
B	0	0	0	0	0
W	0	0	0	0	0
E	0	0	0	0	0
R	0	0	0	0	0

그럼 로직은 간단하게 다음과 같을 것이다.

• 2중 for문으로 문자열을 하나씩 비교
  • 만약 두 값이 같으면 i - 1 , j - 1 값에서 +1
• 2차원 배열에서 최대 값이 최장 공통 부분 문자열이다.

두 값이 같으면 i - 1, j - 1 값에서 +1을 하는 이유는 다음과 같다.
gcr
  ^
pcr
  ^
만약 두 문자열 r을 비교 중이고 서로 같다. 
그럼 gc와 pc 의 최장 공통 부분 문자열에서 r 이라는 문자열을 1개 더한 값이 바로
gcr, pcr 의 최장 공통 부분 문자열이 될 것이다.

전체 풀이

    let fs = require("fs");
    let input = fs.readFileSync("/dev/stdin").toString().trim().split("\n");
    const FirstString = input.shift();
    const SecondString = input.shift();

    class LCString {
        constructor(StringA, StringB) {
            this.Alength = StringA.length;
            this.Blength = StringB.length;
            this.LcsMap = new Array(this.Alength + 1);
          	// 2차원 배열 초기화
            for (let i = 0; i < this.LcsMap.length; i++) {
                this.LcsMap[i] = new Array(this.Blength + 1).fill(0);
            }
          	// 배열의 최대 값을 바로바로 저장하기 위해
            this.Max = 0;
            this.FillLcsMap(StringA, StringB);
        }
		// 배열을 채우기 위해 2개의 문자열 비교하는 함수
        FillLcsMap(A, B) {
            for (let i = 0; i < this.Alength; i++) {
                for (let j = 0; j < this.Blength; j++) {
                  	// 한단계 전의 문자열에서의 최장 공통 부분 문자열 저장
                    const LastValue = this.LcsMap[i][j] + 1;
                    if (A[i] === B[j]) {
                        this.LcsMap[i + 1][j + 1] = LastValue;
                      	// 만약 Max 값이 다음 값보다 작으면 갱신
                        if (this.Max < LastValue) this.Max = LastValue;
                    }
                }
            }
        }

        GetMax() {
            return this.Max;
        }

    }

    const LCS = new LCString(FirstString, SecondString);
    console.log(LCS.GetMax());

🧐 후기

---

전에 풀었던 LCS 알고리즘을 다시 복습할 수 있었던 문제였다.
이번 문제를 풀고 확인했는데 통과는 했으나, 시간이 600ms 가 넘어서 깜짝 놀라서 체점 현황으로 혹시 내가 잘못풀었나 확인하기 위해 다른 사람들의 시간을 확인하고 다들 비슷한 것을 보고 안심했다.
2중 for문으로 문자열을 하나하나 비교하다보니 아무래도 시간이 좀 걸리는 것 같다.