백준 9252번: LCS 2 (Python, C++)

접근

이전에 풀었던 LCS 문제는 공통 수열의 길이만 필요했다면, 이번 문제에서는 그 수열을 저장해야 한다.

최장 공통 수열(LCS) 기본 문제: 2021.03.30 - [코딩/백준 (Python)] - 백준 9251번: LCS (Python)

백준 9251번: LCS (Python)

이전에 풀었던 코드와 유사하게 작성하되 dp에 그 길이만을 저장하는 것이 아니라 해당 시점의 공통 수열 그 자체를 저장하도록 코드를 작성하였다.

---

이전에 파이썬으로 풀었었는데 재채점되어 시간초과로 실패가 떠서 C++로 다시 풀어보았다.

결론적으로 말하자면 dp에 문자열을 저장하는 것이 시간이 많이 걸리므로 그렇게 풀면 안되고, LCS 기본문제와 같이 LCS의 길이만 dp에 저장한 후, dp 배열을 이용하여 공통 문자열을 역추적해서 저장해야한다.

dp의 맨아래 오른쪽칸부터 탐색하기 시작하여 위쪽 칸과 값이 같으면 위로 이동, 왼쪽 칸과 값이 같으면 왼쪽으로 이동, 둘다 아니라면 해당 칸의 문자를 저장하고 대각선으로 이동한다. 탐색하는 칸이 0이 되면 탐색을 종료한다.

코드

C++ 코드

#include <iostream>
#include <string>

using namespace std;

#define endl '\n'
#define MAX_L 1001

string str1, str2, ans_str;
int dp[MAX_L][MAX_L];

int MaxVal(int a, int b) {
    if (a >= b) {
        return a;
    } else {
        return b;
    }
}

int main(int argc, char** argv) {
    // freopen 주석 처리
    freopen("input.txt", "r", stdin);

    cin >> str1 >> str2;
    str1 = ' ' + str1;
    str2 = ' ' + str2;

    // 기본 LCS와 동일하게 공통최대문자열 길이 dp에 저장
    for (int i = 1; i < str1.size(); i++) {
        for (int j = 1; j < str2.size(); j++) {
            if (str1[i] == str2[j]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;
            } else {
                dp[i][j] = MaxVal(dp[i - 1][j], dp[i][j - 1]);
            }
        }
    }

    // dp의 맨아래 오른쪽칸에서부터 역추적하여 공통 문자열을 탐색
    int row = str1.size() - 1;
    int col = str2.size() - 1;
    while (dp[row][col]) {
        if (dp[row][col] == dp[row - 1][col]) {
            row--;
        } else if (dp[row][col] == dp[row][col - 1]) {
            col--;
        } else {
            ans_str = str1[row] + ans_str;
            row--;
            col--;
        }
    }

    cout << dp[str1.size() - 1][str2.size() - 1] << endl;
    if (dp[str1.size() - 1][str2.size() - 1] != 0) cout << ans_str << endl;

    return 0;
}

Python 코드

import sys

m = [0] + list(sys.stdin.readline().rstrip())
n = [0] + list(sys.stdin.readline().rstrip())
dp = [[0 for _ in range(len(n))] for __ in range(len(m))]
for i in range(1, len(m)):
    for j in range(1, len(n)):
        if m[i] == n[j]:
            dp[i][j] = dp[i - 1][j - 1] + 1
        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

row = len(m) - 1
col = len(n) - 1
ans = ""
while dp[row][col]:
    if dp[row][col] == dp[row - 1][col]:
        row -= 1
    elif dp[row][col] == dp[row][col - 1]:
        col -= 1
    else:
        ans = m[row] + ans
        row -= 1
        col -= 1

print(dp[len(m) - 1][len(n) - 1])
print(ans)

기존 시간초과 Python 코드

import sys

m = [0] + list(sys.stdin.readline().rstrip())
n = [0] + list(sys.stdin.readline().rstrip())
dp = [['' for _ in range(len(n))] for __ in range(len(m))]
for i in range(1, len(m)):
    for j in range(1, len(n)):
        if m[i] == n[j]:
            dp[i][j] = dp[i - 1][j - 1] + m[i]
        else:
            if len(dp[i - 1][j]) > len(dp[i][j - 1]):
                dp[i][j] = dp[i - 1][j]
            else:
                dp[i][j] = dp[i][j - 1]
print(len(dp[len(m) - 1][len(n) - 1]))
print(dp[len(m) - 1][len(n) - 1])

더 생각해 볼 것?

...

코드나 내용 관련 조언, 부족한 점 및 질문 언제든 환영합니다!