백준 LCS 2

문제

내가 생각했을때 문제에서 원하는부분

첫째 줄과 둘째 줄에 두 문자열이 주어진다.
문자열은 알파벳 대문자로만 이루어져 있으며,
최대 1000글자로 이루어져 있다.
첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를,
둘째 줄에 LCS를 출력한다.
LCS가 여러 가지인 경우에는 아무거나 출력하고,
LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

내가 이 문제를 보고 생각해본 부분

BufferedReader를 통해 입력을 받는다.
DP 테이블 생성해준다.
LCS 길이 계산: 두 문자열의 LCS 길이를 계산하여 DP 테이블에 저장한다.
LCS의 길이 출력: 계산된 LCS의 길이를 출력한다.
LCS 문자열 생성: DP 테이블을 이용해 LCS 문자열을 생성한다.
LCS 문자열을 뒤집어서 출력: 생성된 LCS 문자열을 뒤집어서 출력한다.

LCS (Longest Common Subsequence)

LCS (Longest Common Subsequence)란 최장 공통 부분 문자열이다. Subsequence의 뜻은 부분 수열 이라는 의미로 문자열이 연속적이지 않아도 된다는 의미이다.
두 문자열 a, b를 비교할 때 공통 부분 수열 중 길이가 가장 긴 부분 수열을 의미한다.

문자열 ABCDEF와 GBCDFE를 이용하여 차이점을 예시로 들어보면
해당 예시에서 최장 공통 부분수열(Longest Common Subsequence)은 BCDF, BCDE가 될 수 있다. 부분수열이기 때문에 문자 사이를 건너뛰어 공통되면서 가장 긴 부분 문자열을 찾으면 된다. 최장 공통 부분 문자열(Longest Common Substring)은 BCD이다. 부분문자열이 아니기 때문에 한번에 이어져있는 문자열만 가능하다.

코드로 구현

package baekjoon.baekjoon_23;

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

// 백준 9252번 문제
public class Main815 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String str1 = br.readLine();
        String str2 = br.readLine();

        int len1 = str1.length();
        int len2 = str2.length();

        // DP 테이블 생성
        int[][] dp = new int[len1 + 1][len2 + 1];

        // LCS 길이 계산
        for(int i = 1; i <= len1; i++) {
            for(int j = 1; j <= len2; j++) {
                if(str1.charAt(i - 1) == str2.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]);
                }
            }
        }

        // LCS 길이 출력
        System.out.println(dp[len1][len2]);

        // LCS 문자열 생성
        StringBuilder lcs = new StringBuilder();
        int i = len1;
        int j = len2;

        while(i > 0 && j > 0) {
            if(str1.charAt(i - 1) == str2.charAt(j - 1)) {
                lcs.append(str1.charAt(i - 1));
                i--;
                j--;
            } else {
                if(dp[i - 1][j] >= dp[i][j - 1]) {
                    i--;
                } else {
                    j--;
                }
            }
        }

        // LCS 문자열을 뒤집어서 출력
        if(lcs.length() > 0) {
            System.out.println(lcs.reverse().toString());
        }
        br.close();
    }
}

마무리

코드와 설명이 부족할수 있습니다. 코드를 보시고 문제가 있거나 코드 개선이 필요한 부분이 있다면 댓글로 말해주시면 감사한 마음으로 참고해 코드를 수정 하겠습니다.