9252 - LCS 2 (Java)

🔗 문제 링크

---

📝 문제 설명

두 문자열 A와 B가 주어졌을 때,
두 문자열의 최장 공통 부분 수열(Longest Common Subsequence, LCS) 을 구하는 문제임.
예를 들어, A = "ACAYKP", B = "CAPCAK"인 경우 LCS는 "ACAK"임.

---

✅ 풀이 접근 방식 및 시도한 방법들

첫 번째 시도: StringBuilder를 이용한 누적 방식

• 방법:
  LCS의 길이가 갱신될 때마다 StringBuilder에 해당 문자를 추가하는 방식으로 진행함.
• 문제점:
  예를 들어,
  • A = AACAAABAA
  • B = AAACAABAA
    와 같이 반례가 존재하여 올바른 LCS 문자열을 복원하지 못함.

---

두 번째 시도: String[][] 배열을 활용한 DP

• 방법:
  각 DP 상태에서 LCS 문자열 자체를 저장하기 위해 String[][] 이차원 배열을 사용함.
• 문제점:
  DP 테이블의 각 셀마다 문자열을 저장하다 보니 메모리 사용량이 급증하여 메모리 초과가 발생함.

---

최종 해결법: 백트래킹 기법을 활용한 DP

• 방법:
  • DP 테이블 구성:
    • dp[i][j]: A의 처음 i 글자와 B의 처음 j 글자에 대해 구한 LCS의 길이.
    • dpDir[i][j]: LCS의 길이가 갱신될 때, 해당 값이 어디서 전이되었는지 기록하는 포인터 배열.
      • 1: 대각선 (A[i-1] == B[j-1])에서 갱신됨
      • 2: 왼쪽 (dp[i][j-1])에서 갱신됨
      • 3: 위쪽 (dp[i-1][j])에서 갱신됨
  • 백트래킹:
    dpDir 배열을 사용해, 오른쪽 하단에서 시작하여 역으로 추적함으로써 최종 LCS 문자열을 복원함.
• 장점:
  각 DP 상태에 대해 문자열 전체를 저장하는 대신,
  전이 정보(포인터)만 저장하여 메모리 사용량을 크게 줄였음.

---

🔍 최종 코드 구현

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

public class Main {
    private static StringTokenizer st;
    private static StringBuilder sb = new StringBuilder();
    private static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    
    public static void main(String[] args) throws IOException {
        String A = br.readLine();
        String B = br.readLine();
        
        // dp 배열: LCS의 길이를 저장
        int[][] dp = new int[A.length() + 1][B.length() + 1];
        // dpDir 배열: 백트래킹 포인터 저장 (어느 방향에서 갱신되었는지)
        int[][] dpDir = new int[A.length() + 1][B.length() + 1];
        
        // DP 테이블 채우기
        for (int i = 1; i <= A.length(); i++) {
            for (int j = 1; j <= B.length(); j++) {
                if (A.charAt(i - 1) == B.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                    dpDir[i][j] = 1; // 대각선 방향
                } else {
                    if (dp[i][j - 1] > dp[i - 1][j]) {
                        dp[i][j] = dp[i][j - 1];
                        dpDir[i][j] = 2; // 왼쪽 방향
                    } else {
                        dp[i][j] = dp[i - 1][j];
                        dpDir[i][j] = 3; // 위쪽 방향
                    }
                }
            }
        }
        
        // LCS의 길이 출력
        System.out.println(dp[A.length()][B.length()]);
        
        // LCS 문자열 복원 (백트래킹)
        if (dp[A.length()][B.length()] != 0) {
            int x = A.length();
            int y = B.length();
            while (x > 0 && y > 0) {
                if (dpDir[x][y] == 1) {
                    sb.append(A.charAt(x - 1));
                    x--;
                    y--;
                } else if (dpDir[x][y] == 2) {
                    y--;
                } else {
                    x--;
                }
            }
            sb.reverse();
            System.out.println(sb.toString());
        }
    }
}

---

✅ 결론

• 초기 시도:
  StringBuilder를 직접 사용하여 누적하는 방식은 반례로 인해 실패하였음.
• 두 번째 시도:
  String[][] 배열로 DP 상태마다 LCS 문자열을 저장하는 방식은 메모리 초과 문제를 야기함.
• 최종 해결:
  DP로 LCS의 길이를 계산하고, dpDir 배열에 전이 정보를 기록한 후 백트래킹으로 LCS를 복원하는 방식으로 문제를 해결함.
  이 방법은 메모리 사용을 최소화하면서도 올바른 LCS 문자열을 복원할 수 있음.