[JS] 백준 9251번 : LCS - DP문제

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

9251번: LCS

 

LCS 참고

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 Subsequence)을 말합니다만, 

최장 공통 문자열(Longest Common Substring)을 말하기도 합니다.

 

부분수열은 연속되지 않은 것

문자열은 연속된 것이다.

 

 

 

📋풀이방법

1. 2차원배열에 0으로 채운 DP 배열을 만든다, 이때 0번째 인덱스는 비워준다

2. 첫번째 문자열 str1이 열에 해당하고( i열 )

3. 두번째 문자열이 str2가 행에 해당한다.

4. 행을 기준으로 열에있는 문자와 같은지 비교한다.

 5. 같다면 대각선 왼쪽위의 값에서 +1을 해준다

 6. 다르다면 왼쪽과 위쪽부분의 값을 가져와 둘 중 큰 값을 가져온다.

7. 모든 행을 거치면 배열의 마지막에 답이 나오게 된다.

 

📝그림으로 설명

-만약 같은 알파벳을 만난 경우

-그 다음 상황에 수열이 성사되는 경우

-> 이 방식으로 반복해나가면 제일 마지막부분에 답이 나온다.

 

1. LCS[i - 1][j]와 LCS[i][j - 1]는 어떤 의미인가?

부분수열은 연속된 값이 아닙니다. 때문에 현재의 문자를 비교하는 과정 이전의 최대 공통 부분수열은 계속해서 유지됩니다. '현재의 문자를 비교하는 과정' 이전의 과정이 바로 LCS[i - 1][j]와 LCS[i][j - 1]가 됩니다.

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

const str1 = input[0].split('');
const str2 = input[1].split('');
const len = str1.length;
const len2 = str2.length;
// 2차원 배열 생성

// 0으로 초기화
const DP = Array.from(Array(2000), () => Array());

// 모든 행, 열 0으로 초기화
for(let i = 0; i <= len; i++) {
    for(let j = 0; j <= len2; j++) {
        DP[i][j] = 0 
    }
}

/* 부분수열은 연속된 값이 아니다! */

for(let i = 1; i <= len; i++) {
    for(let j = 1; j <= len2; j++) {   
        // i - 1, j - 1이 같은 경우, 알파벳이 같은 경우
        if(str1[i - 1] === str2[j - 1]) {
            // 대각선 왼쪽 위의 값에서 + 1
            DP[i][j] = DP[i - 1][j - 1] + 1
        } else {
            // 아니면, [i][j - 1], [i - 1][j]의 값에서 큰 값 가져오기
            //알파벳이 같지않으면 2차원 배열 기준으로 왼쪽과 위 부분 중 큰 값을 가져온다
            //이는 
            DP[i][j] = Math.max(DP[i][j - 1], DP[i - 1][j])
        }
    }
}

console.log(DP[len][len2])

 

 

만약 위에서만든 DP배열로 LCS 문자열을 출력하고 싶다면?

 

 📋풀이방법

 

 

참고를 보고 풀었다

1. 맨 마지막 좌표에서 위 아래 부분을 검사한다

2. 검사하면서 두 부분이 같지 않을 때를 카운트한다

 - 카운트가 2가 되는 경우 : 해당 열에 있는 문자열의 x-1한 부분이 정답 문자이므로 추출한다. 

  그리고 좌표는 대각선으로 이동한다

 - 카운트가 2가 되지  않은 경우 : 정답 문자가 없으므로 같은 숫자가 있던 곳으로 가야한다.

  ->만약 위 아래가 모두 같은 숫자일 경우가 있는데 이는 상관없다

  -> 열에 있는 문자열의 x-1한 부분을 추출하므로 ->이 부분에서 잠시 고민했다.

3. 만약 DP[y][x]가 0인 부분에 도달하면 끝난 것이므로 반복을 멈춰준다.

 

 

 

🤟내 제출

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let input = fs.readFileSync(filePath).toString().trim();
input=input.replace(/\r/g,"").split("\n");

const str1 = input[0].split('');
const str2 = input[1].split('');
const len = str1.length;
const len2 = str2.length;
// 2차원 배열 생성
/*
    C A P C A K

A
C
A
Y
K
P
*/
// 0으로 초기화
const DP = Array.from({length:len+1}, () => Array(len2+1).fill(0));

/* 부분수열은 연속된 값이 아니다! */

for(let i = 1; i <= len; i++) {
    for(let j = 1; j <= len2; j++) {   
        // i - 1, j - 1이 같은 경우, 알파벳이 같은 경우
        if(str1[i - 1] === str2[j - 1]) {
            // 대각선 왼쪽 위의 값에서 + 1
            DP[i][j] = DP[i - 1][j - 1] + 1
        } else {
            // 아니면, [i][j - 1], [i - 1][j]의 값에서 큰 값 가져오기
            //알파벳이 같지않으면 2차원 배열 기준으로 왼쪽과 위 부분 중 큰 값을 가져온다
            //이는 
            DP[i][j] = Math.max(DP[i][j - 1], DP[i - 1][j])
        }
    }
}

let dx=[0,-1];
let dy=[-1,0];


let y=len;
let x=len;
let visited=Array.from({length:len+1},()=>Array(len+1).fill(0));

let result=[];
while(1){
    let cnt=0;
    let temp=[];
    for(var i=0;i<2;i++){
        let nx=x+dx[i];
        let ny=y+dy[i];
        if(nx>=0 && ny>=0 && nx<len+1 && ny<len+1){
            if(visited[ny][nx]==0){
                visited[ny][nx]=1;
                if(DP[ny][nx]!=DP[y][x]){
                    cnt++;
                }
                else{
                    temp=[ny,nx];
                }
            }
        }
    }
    if(cnt==2){
        result.push(str2[x-1]);
        y=y-1;
        x=x-1;
        
    }else{
        y=temp[0]
        x=temp[1]
    }
    if(DP[y][x]==0){
        break;
    }
}
console.log(result.reverse().join())