[BOJ 9252] LCS 2 (최장 공통 부분 수열)

문제

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

9252번: LCS 2

 

풀이

2021.11.08 - [Problem Solving/BOJ] - [BOJ 9251] LCS 최장 공통 부분 수열 문제 (Java)

[BOJ 9251] LCS 최장 공통 부분 수열 문제 (Java)

위 문제와 풀이는 동일하다. 

다만 여기서는 LCS의 값도 표시해주어야 한다. 

dp 배열을 모두 채운 후 역추적을 한다. 

 

출처: 위키백과

 

배열의 마지막 값부터 역추적을 한다.

현재 인덱스의 각 수열의 문자가 다를 경우,

현재 인덱스의 위와 좌측 값을 비교하여 동일한 값을 가지는 인덱스로 이동한다. (처음 dp에 넣을 때랑 반대로)

문자 값이 서로 같은 경우, dp값을 넣었을 때랑 반대 방향의 대각선으로 이동한다. 

        while(true){
            if(s1.charAt(x-1) == s2.charAt(y-1)){
            	// 값이 동일할 때
                sb.insert(0, s1.charAt(x-1));
                x = x-1;
                y = y-1;
            } else {
            	// 값이 다를 때
                if(dp[x][y] == dp[x-1][y]){
                    x = x-1;
                } else {
                    y = y-1;
                }
            }
            if(x == 0 || y == 0) break;
        }

 

소스코드

package lcs;

import java.io.BufferedReader;
import java.io.InputStreamReader;

public class BOJ9252 {

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String s1 = br.readLine();
        String s2 = br.readLine();

        int n = s1.length();
        int m = s2.length();
        int[][] dp = new int[n+1][m+1];
        for(int i = 1; i <= n; i++){
            for(int j = 1; j <= m; j++){
                if(i == 0 || j == 0){
                    dp[i][j] = 0;
                    continue;
                }
                if(s1.charAt(i-1) == s2.charAt(j-1)){
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j-1], dp[i-1][j]);
                }
            }
        }

        int max = dp[n][m];
        StringBuilder sb = new StringBuilder();
        int x = n;
        int y = m;
        while(true){
            if(s1.charAt(x-1) == s2.charAt(y-1)){
                sb.insert(0, s1.charAt(x-1));
                x = x-1;
                y = y-1;
            } else {
                if(dp[x][y] == dp[x-1][y]){
                    x = x-1;
                } else {
                    y = y-1;
                }
            }
            if(x == 0 || y == 0) break;
        }
        System.out.println(max);
        if(max > 0){
            System.out.println(sb.toString());
        }
    }
}