프로그래머스: 공통 부분 문자열 - javascript(문자열, dp)

문제 출처 

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

 

문제 풀이 

 

dp 2차원 그래프를 그린다. 

str1 = 'GBCDFE'

str2 = 'ABCDEF'

인 상황이다. 

 

각각 str의 길이를 이렇게 설정해주자. 

let n =  str1.length 

let m = str2.length 

 

우리는 dp를 이용할 건데 

dp 2차원 그래프를 생성하자. 

세로:n+1  ,가로: m+1 길이를 가진 그래프일 것이다 

 

모두 0으로 채울 것이다. 

 

아래 그림과 같이 특히 idx 0은 무조건 0인데 무슨 의미일까? 

''과 'ABCDEF'를 비교하면, 같은 부분이 없고, 

'GBCDFE'와 ''를 비교하면, 같은 부분이 없다는 의미다. 

 

아래 분홍색 부분은 어떤 것을 뜻하는가? 

'GBCDFE'에서의 'GBC'

'ABCDEF'에서의 'AB'

까지를 비교했을 때, 연속된 문자 부분 수열의 최대값을 의미한다. 

저 값은 어떻게 구할 수 있을까? 

 

 

신기하게도 아래 파랑 부분이 도움이 된다. 

 

분홍색 부분인 'GBCDFE'에서의 'GBC' 'ABCDEF'에서의 'AB' 의 이전 비교는 어디가 되는가? 

파란색 부분인 'GBCDFE'에서의 'GB' 'ABCDEF'에서의 'A' 를 비교했을 때가 된다.  

 

그렇담 파란색 부분의 값을 이용하면 된다는 뜻이다. 

현재 분홍색 부분인 'GBCDFE'에서의 'C' 'ABCDEF'에서의 'B' 를 비교하고 있는 중이였다. 

두 문자는 다르다. 그러니, 그대로 0이 되면 된다. 

 

 

 

예시를 하나 더 들어보자. 

만약 아래와 같이 값이 같을 때는 어떻게 하면 되나? 

 

 'GBCDFE'에서의 'B' 'ABCDEF'에서의 'B' 를 비교하고 잇는 부분이다. 

 

 

이전의 비교는 어느 부분이 되는가?

 'GBCDFE'에서의 'G' 'ABCDEF'에서의 'A' 이다. 

파란색 부분이다. 

그 값은 0이다. 즉, 현재 비교중인 분홍색 부분 이전에는 연속적으로 이어진 문자가 0개라는 뜻. 

그렇담? 현재 분홍색 부분에서 B는 서로 같은 문자이니, 이전의 비교 + 1을 해주면 된다. 

즉, 

dp[i][j] = dp[i-1][j-1] + 1

이 된다. 

 

 

 

이 분의 블로그를 본다면, 완벽히 이해가 가지 않을까 싶다. 

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

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

 

정답 코드 

const [str1, str2] = require('fs').readFileSync('/dev/stdin').toString().trim().split('\n'); 

function solution(str1, str2){
    let n = str1.length; 
    let m = str2.length; 
    let dp = Array.from({length: n+1}).map(() => new Array(m+1).fill(0))
     
    let answer = 0
    
    for(let i=1; i<n+1; i++){
        for(let j=1; j<m+1; j++){
            if(str1[i-1] === str2[j-1]){
                dp[i][j] = dp[i-1][j-1] + 1
                answer = Math.max(answer, dp[i][j])
            }
        }
    }
    return answer; 
    }

console.log(solution(str1, str2))