[Gold IV] LCS 2 - 9252 (Java)

문제 요약

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

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

---

문제 분석

• 두 문자열 A와 B의 모든 위치를 검사하면서, 만약 두 문자가 같다면 이전 위치의 LCS 길이에 1을 더하고, 그렇지 않다면 이전 위치에서의 LCS 길이 중 큰 값을 저장한다.
• 이 과정을 통해 얻은 2차원 배열 dp의 마지막 요소 dp[A.length][B.length]가 두 문자열의 LCS 길이가 된다.
• LCS를 출력하기 위해, 문자열 A와 B의 마지막 위치에서 시작해 첫 위치까지 역순으로 이동하면서, 두 문자가 같을 경우 해당 문자를 스택에 추가하고, 그렇지 않을 경우 LCS 길이가 더 큰 쪽으로 이동한다.
• 마지막으로, 스택에서 모든 문자를 꺼내어 출력하면 그것이 LCS가 된다.

참고 블로그

 https://velog.io/@emplam27/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B7%B8%EB%A6%BC%EC%9C%BC%EB%A1%9C-%EC%95%8C%EC%95%84%EB%B3%B4%EB%8A%94-LCS-%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-Longest-Common-Substring%EC%99%80-Longest-Common-Subsequence

[알고리즘] 그림으로 알아보는 LCS 알고리즘 - Longest Common Substring와 Longest Common Subsequence

---

코드

package Week20;

import java.io.*;
import java.util.Stack;

public class BOJ_9252 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        char[] A = br.readLine().toCharArray();
        char[] B = br.readLine().toCharArray();
        // 이 배열은 각 위치에서 가장 긴 증가하는 부분 수열의 길이를 저장한다.
        int[][] dp = new int[A.length + 1][B.length + 1];
        for (int r = 1; r <= A.length; r++) {
            for (int c = 1; c <= B.length; c++) {
                if (A[r - 1] == B[c - 1]) {
                    dp[r][c] = dp[r - 1][c - 1] + 1;
                } else {
                    dp[r][c] = Math.max(dp[r - 1][c], dp[r][c - 1]);
                }
            }
        }
        bw.write(String.valueOf(dp[A.length][B.length]));
        bw.newLine();
        // LCS출력
        Stack<Character> stack = new Stack<>();
        int r = A.length - 1;
        int c = B.length - 1;
        while (r >= 0 && c >= 0) {
            if (A[r] == B[c]) {
                stack.push(A[r]);
                r--;
                c--;
            } else {
                if (dp[r][c + 1] > dp[r + 1][c]) {
                    r--;
                } else {
                    c--;
                }
            }
        }
        while (!stack.empty()) {
            bw.write(stack.pop());
        }
        bw.newLine();
        bw.close();
    }
}

---