백준 9252번: LCS 2 (JAVA)

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

9252번: LCS 2

문제

LCS(Longest Common Subsequence, 최장 공통 부분 수열)문제는 두 수열이 주어졌을 때, 모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

예를 들어, ACAYKP와 CAPCAK의 LCS는 ACAK가 된다.

입력

첫째 줄과 둘째 줄에 두 문자열이 주어진다. 문자열은 알파벳 대문자로만 이루어져 있으며, 최대 1000글자로 이루어져 있다.

출력

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다.

LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

 

---

 

풀이

기본적으로 LCS 찾는 방법은 '9251번: LCS'를 통해 이해할 수 있다. 본 문제는 경로를 찾는 문제인데, 찾는 방법은 다음과 같다.

A의 길이가 M, B의 길이가 N일 때, row = M, col = N부터 시작하여(가정: dp를 1부터 시작하였음, dp[M][N]은 언제나 최대값을 갖고 있어서 해당 값에서부터 찾기 시작해도 된다.)

1) dp[r][c] = dp[r-1][c] or dp[r][c-1]인 경우: A의 r-1번째 자리와 B의 c-1번째 자리의 알파벳은 같지 않다. 경우를 나누어,

1.  dp[r][c] == dp[r-1][c]: A의 r-1번째 자리 알파벳은 LCS에 포함되지 않는다. 따라서 r을 1씩 줄여서 계속 탐색한다,
2.  dp[r][c] == dp[r][c-1]: B의 c-1번째 자리 알파벳은 LCS에 포함되지 않는다. 따라서 c를 1씩 줄여서 계속 탐색한다.

2) 1)이 아닌 경우: 해당 경우에는 반드시 dp[r][c] = dp[r-1][c-1]이며, 이는 A의 r-1번째 알파벳(혹은 B의 c-1번째 알파벳)이 LCS에 포함된다는 것을 의미한다. 따라서 이 알파벳을 저장하며(LCS는 찾은 알파벳의 역순일 테므로, 스택같은 자료구조를 활용할 수 있을 것이다.), r, c를 1씩 줄인다.

 

r 혹은 c가 0이 될 때까지 진행한다.

 

배울 점 

경로를 구하겠다고 prev[M+1][N+1][2]을 선언하여 풀었는데,  인접한 dp값의 특성을 이용하면 그대로 경로룰 역추적할 수 있더라. 이 방법이 memory complexity, time complexity 모두 우월하다(big-O 관점에서는 동일하나, 2배 차이난다).

 

코드

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

public class Baekjoon9252_LCS2 {

    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        String A = br.readLine();
        String B = br.readLine();
        int M = A.length(), N = B.length();
        Stack<String> letters = new Stack<>();

        int[][] dp = new int[M+1][N+1];
        StringBuilder sb = new StringBuilder();

        for (int i = 1; i <= M; i++) {
            for (int j = 1; j <= N; j++) {
                if (A.charAt(i-1) == B.charAt(j-1)) {
                    dp[i][j] = 1 + dp[i-1][j-1];
                }
                else {
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
            }
        }
        sb.append(dp[M][N]+"\n");

        int row = M, col = N;
        while (row > 0 && col > 0) {
            if (dp[row][col] == dp[row-1][col]) {
                row--;
                continue;
            }
            if (dp[row][col] == dp[row][col-1]) {
                col--;
                continue;
            }
            letters.add(A.substring(row-1, row));
            row--;
            col--;
            continue;
        }
        while (!letters.isEmpty()) {
            sb.append(letters.pop());
        }

        System.out.println(sb);
    }

}