[JS][백준]5582_공톤 부분 문자열

문제 번호

5582번: 공통 부분 문자열

 

 

 

알고리즘 분류

• 다이나믹 프로그래밍
• 문자열

 

문제 풀이

 많이 접해본 문제이다. 문제를 해결하기위해서 2차원 배열을 사용할거다. 2차원배열의 x축과 y축을 각각 주어진 문자열이라고 생각한다. abcd 와 bcda가 있다면 다음과 같다.

	a	b	c	d
b	X
c
d
a

 이제 X 지점부터 오른쪽아래로 탐색하면서 2차원 배열을 채워준다. (x,y)일때 두 문자열의 문자가 같다면 '왼쪽대각선위 + 1' 의 값을 (x,y)에 넣어주고, 서로 다르다면 0을 넣어준다.

 

세로길이 가로길이가 각각 (문자열의 길이 + 1 ) 가 되도록 생성한다.

   let arr = new Array(s1.length + 1).fill(null).map(_ => new Array(s2.length + 1).fill(0));

0	0	0	0	0	0
0	b !== a, 이므로 0	b==b, 이므로 1	0	0	0
0	0	0	c==c이므로, 2
0
0
0

 2차원 배열을 채워가면서 가장 큰 값이 나올때마다 정답을 갱신해준다. 배열의 인덱스와 문자열의 인덱스에 주의해서 진행하면 어려운 부분없이 해결할 수 있다.

 

전체코드

const input = require('fs').readFileSync('input.txt').toString().trim().split('\n');

function sol(s1, s2) {
   let answer = 0;

   let arr = new Array(s1.length + 1).fill(null).map(_ => new Array(s2.length + 1).fill(0)); // 문자열이 서로 같으면 대각선에서 +1, 다르면 0 으로 처리한다.
   for (let i = 0; i < s1.length; i++) { // 문자열은 0번 인덱스부터 확인하지만 2차원 배열은 (1,1)부터 사용할것이다.
      for (let j = 0; j < s2.length; j++) {
         if (s1[i] === s2[j]) {
            arr[i+1][j+1] = arr[i][j] + 1;
         } else {
            arr[i+1][j+1] = 0;
         }
         if (arr[i+1][j+1] > answer)
            answer = arr[i+1][j+1];
      }
   }

   return answer;
}
function main() {
   let [s1, s2] = [input[0].trim(), input[1].trim()];
   console.log(sol(s1, s2));
}
main();

특이사항