[백준] 9252번 - LCS 2 [Java][C++]

문제 링크

---

1. 문제 풀이

LCS의 길이 뿐만 아니라 실제 LCS까지 출력해야 하는 문제다. LCS의 길이는 2차원 dp 테이블의 가장 마지막 행, 마지막 열이 온전한 두 문자열의 LCS의 길이를 담고 있으니 여기서 구하면 되고, 실제 LCS는 이 dp 테이블을 역추적하는 방식으로 구할 수 있다. 최종적으로 구하면 실제 LCS의 역순으로 조회되므로 이를 뒤집으면 실제 LCS를 구할 수 있다.

---

2. 코드

1. Bottom-Up dp [Java]

dp 테이블 앞에 패딩을 한 칸씩 줬다.

import java.io.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        char[] str1 = br.readLine().toCharArray();
        char[] str2 = br.readLine().toCharArray();
        int N = str1.length;
        int M = str2.length;

        int[][] dp = new int[1 + N][1 + M];
        for (int i = 1; i <= N; i++) {
            for (int j = 1; j <= M; j++) {
                if (str1[i - 1] == str2[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]);
                }
            }
        }

        sb.append(dp[N][M]).append("\n");
        if (dp[N][M] != 0) sb.append(traceback(str1, str2, dp));

        System.out.println(sb);
    }

    static String traceback(char[] str1, char[] str2, int[][] dp) {
        StringBuilder sb = new StringBuilder();

        int r = str1.length - 1;
        int c = str2.length - 1;

        while (r >= 0 && c >= 0) {
            if (str1[r] == str2[c]) {
                sb.append(str1[r]);
                r--;
                c--;
            } else {
                if (dp[r][c + 1] > dp[r + 1][c]) {
                    r--;
                } else {
                    c--;
                }
            }
        }

        return sb.reverse().toString();
    }
}

2. Bottom-Up dp [C++]

dp 테이블 앞에 패딩을 한 칸씩 줬다.

#include <bits/stdc++.h>
using namespace std;

string traceback(const string& s1, const string& s2, const vector<vector<int>>& dp) {
    string res;

    int r = s1.size() - 1;
    int c = s2.size() - 1;

    while (r >= 0 && c >= 0) {
        if (s1[r] == s2[c]) {
            res.push_back(s1[r]);
            r--;
            c--;
        } else {
            if (dp[r][c + 1] > dp[r + 1][c]) {
                r--;
            } else {
                c--;
            }
        }
    }

    reverse(res.begin(), res.end());
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    string s1, s2;
    cin >> s1 >> s2;

    int n = s1.size();
    int m = s2.size();

    vector<vector<int>> dp(1 + n, vector<int>(1 + m));
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            if (s1[i - 1] == s2[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    cout << dp[n][m] << '\n';
    cout << traceback(s1, s2, dp);
}

---

3. 풀이 정보

1. Bottom-Up dp [Java]

언어	시간	메모리	코드 길이
Java 11	136 ms	18332 KB	1481 B

2. Bottom-Up dp [C++]

언어	시간	메모리	코드 길이
C++ 17	4 ms	6004 KB	1104 B

---