[Python - Dynamic Programming] 9252 LCS 2

📌 문제

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

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

📌 입력

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

📌 출력

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

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

📌 문제 풀이

👨‍🏫 접근

9251 LCS 문제의 확장판. 개수를 세면서 문자를 추가해주면 된다.

👨‍🏫 문제 풀이

📄 전체 코드

import sys
input = sys.stdin.readline

w1 = input().strip()
w2 = input().strip()

len_w1, len_w2 = len(w1), len(w2)
d = [[0, ""] for _ in range(len_w2)]

for i in range(len_w1):
    tmp = 0
    word = ""
    for j in range(len_w2):
        if tmp < d[j][0]:
            tmp = d[j][0]
            word = d[j][1]
        elif w1[i] == w2[j]:
            d[j][0] = tmp + 1  # 개수 추가는 맞음
            d[j][1] = word + w1[i]

print(*max(d), sep="\n")

📄 준비

import sys
input = sys.stdin.readline

w1 = input().strip()
w2 = input().strip()

len_w1, len_w2 = len(w1), len(w2)
d = [[0, ""] for _ in range(len_w2)]

이번에는 2차원 리스트로 생성해준다. 각 요소의 첫 번째 인덱스는 LCS 길이이며, 두 번째 인덱스는 LCS 문자열이다. 문자열 연산을 할 것이기 때문에 빈 문자열로 초기화한다.

📄 풀이

for i in range(len_w1):
    tmp = 0
    word = ""
    for j in range(len_w2):
        if tmp < d[j][0]:
            tmp = d[j][0]
            word = d[j][1]
        elif w1[i] == w2[j]:
            d[j][0] = tmp + 1  # 개수 추가는 맞음
            d[j][1] = word + w1[i]

print(*max(d), sep="\n")

tmp와 함께 word라는 임시 변수 두 개를 설정했다. LCS 개수를 순회하면서 늘 최대로 유지하기 위해서 tmp보다 값이 클 때 그 값으로 저장해주고 임시 단어도 저장해준다. 그 후에 일치하는 문자열을 찾으면 길이를 1 늘려주고, 임시 변수와 함께 그 일치하는 문자열을 그대로 추가해준다.

📌 총평

 

날로 먹은 문제. 호로록~