b9295. LCS2

 

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

 

 

 

두 문자열 간의 최장 공통 부분 수열(Longest Common Subsequence, LCS)을 구하는 문제다. LCS는 두 문자열에서 순서를 유지하면서 삭제 가능한 가장 긴 공통 부분 문자열을 의미한다.
이를 동적 계획법(DP)을 사용하여 효율적으로 계산하고자 했다.

먼저 두 문자열 s1과 s2를 입력받고, 두 문자열의 길이를 기반으로 DP 배열을 초기화한다.
dp[i][j]는 문자열 s1의 첫 i글자와 s2의 첫 j글자 간의 최장 공통 부분 수열의 길이를 저장한다.
DP 테이블을 채우는 과정에서,
현재 문자 s1.charAt(i - 1)와 s2.charAt(j - 1)이 같으면
dp[i][j]는 dp[i - 1][j - 1] + 1로 갱신된다.
문자가 다르면, 이전 단계의 값 중 더 큰 값을 가져온다
(즉, dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1])).

DP 테이블이 완성된 후, dp[s1.length()][s2.length()]에는
최장 공통 부분 수열의 길이가 저장된다.
이를 출력한 뒤, 실제 공통 부분 수열을 추출한다.
이를 위해 문자열의 끝에서부터 DP 테이블을 역추적하며
공통된 문자를 찾아 StringBuilder에 추가한다.

공통된 문자는 테이블 값이 증가한 경우에 해당하며,
이 과정을 반복하여 LCS를 역순으로 저장한 후,
최종적으로 뒤집어 올바른 순서로 출력한다.

 

 

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

public class b9252 {
    static String s1, s2;
    static int[][] dp;

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

        int s1Size = s1.length();
        int s2Size = s2.length();

        dp = new int[s1Size + 1][s2Size + 1];

        for (int i = 1; i <= s1Size; i++) {
            for (int j = 1; j <= s2Size; j++) {
                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 - 1][j], dp[i][j - 1]);
                }
            }
        }

        System.out.println(dp[s1Size][s2Size]);

        StringBuilder sb = new StringBuilder();
        int i = s1Size, j = s2Size;
        while (i > 0 && j > 0) {
            if (s1.charAt(i - 1) == s2.charAt(j - 1)) {
                sb.append(s1.charAt(i - 1));
                i--;
                j--;
            } else if (dp[i - 1][j] > dp[i][j - 1]) {
                i--;
            } else {
                j--;
            }
        }

        System.out.println(sb.reverse());
    }
}