[Python] 백준 9252번 LCS 2

9252번: LCS 2

문제

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

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

 

입력

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

출력

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

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

코드

str1 = input()
str2 = input()

dp = [["" for _ in (range(len(str1) + 1))] for _ in range(len(str2) + 1)]

for i in range(1, len(str2) + 1):
    for j in range(1, len(str1) + 1):
        if str1[j-1] == str2[i-1]:
            dp[i][j] = dp[i-1][j-1] + str1[j-1]
        else:
            if len(dp[i-1][j]) < len(dp[i][j-1]):
                dp[i][j] = dp[i][j-1]
            else:
                dp[i][j] = dp[i-1][j]

print(len(dp[len(str2)][len(str1)]))
print(dp[len(str2)][len(str1)])

위 코드의 경우 dp 배열에 문자열을 그대로 저장하기 때문에 PyPy3로 하면 통과할 수 있고 Python3로는 시간 초과가 난다.

dp 배열을 표로 보기 좋게 정리하면 아래의 표와 같다.

	0	A	C	A	Y	K	P
0
C			C	C	C	C	C
A		A	C	CA	CA	CA	CA
P		A	C	CA	CA	CA	CAP
C		A	AC	CA	CA	CA	CAP
A		AA	AC	ACA	ACA	ACA	ACA
K		AA	AC	ACA	ACA	ACAK	ACAK

1. 편하게 하기 위해 처음에는 dp 배열을 모두 빈 문자열로 초기화해준다. 
2. 두번째 문자열의 i-1번째 문자와 첫번째 문자열의 j-1번째 문자가 같다면 dp[i][j]에 dp[i-1][j-1]에 저장되어 있는 문자열에 str1[j-1] (= str2[i-1]) 문자를 붙여서 저장한다.
3. 2번의 과정을 반복하여 dp 배열을 완성시켰을 때 dp[len(str2)][len(str1)]에 최종적으로 저장된 문자열이 우리가 찾는 정답이다.

위에서 Python3로는 시간 초과가 난 문제를 해결하기 위해 이번에는 dp 배열에는 LCS의 길이만을 저장하고 추후에 LCS를 따로 구하는 방식으로 구현하여 보았다.

str1 = input()
str2 = input()

dp = [[0 for _ in (range(len(str1) + 1))] for _ in range(len(str2) + 1)]
ans = ""
for i in range(1, len(str2) + 1):
    for j in range(1, len(str1) + 1):
        if str1[j-1] == str2[i-1]:
            dp[i][j] = dp[i-1][j-1] + 1
        else:
            dp[i][j] = max(dp[i-1][j], dp[i][j-1])

row, col = len(str2), len(str1)           
while len(ans) < dp[len(str2)][len(str1)]:
    if str1[col-1] == str2[row-1] and dp[row-1][col-1] + 1 == dp[row][col]:
        ans = str1[col-1] + ans
        row -= 1
        col -= 1 
    elif dp[row][col] == dp[row-1][col]:
        row -= 1
    elif dp[row][col] == dp[row][col-1]:
        col -= 1
print(dp[len(str2)][len(str1)])
print(ans)

이번에 사용된 dp 배열을 표로 보기 쉽게 나타내면 다음과 같다.

	0	A	C	A	Y	K	P
0	0	0	0	0	0	0	0
C	0	0	1	1	1	1	1
A	0	1	1	2	2	2	2
P	0	1	1	2	2	2	3
C	0	1	2	2	2	2	3
A	0	1	2	3	3	3	3
K	0	1	2	3	3	4	4

위 표의 오른쪽 아래에서부터 거슬러 올라가며 정답 문자열을 찾아주자.

표에서 str1[j-1] == str2[i-1]이고, dp[i-1][j-1] + 1 == dp[i][j]인 경우가 같은 문자가 나와서 부분 수열의 길이가 증가하는 시점이므로 이때의 문자를 ans 문자열에 붙여서 저장해준다. 이때 주의해야할 점은 우리는 dp 배열의 끝에서부터 거꾸로 보고 있으므로 ans 문자열의 가장 앞에 문자를 붙여주어야 한다.