(Python/🥇4)백준알고리즘 9252번: LCS 2

문제 바로가기 

LCS 2

 

문제:

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

입력:

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

 

출력:

첫째 줄에 입력으로 주어진 두 문자열의 LCS의 길이를, 둘째 줄에 LCS를 출력한다. LCS가 여러 가지인 경우에는 아무거나 출력하고, LCS의 길이가 0인 경우에는 둘째 줄을 출력하지 않는다.

풀이:

import sys

sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')

lst1 = [""] + [i for i in sys.stdin.readline().rstrip()]
lst2 = [""] + [i for i in sys.stdin.readline().rstrip()]
dp = [[""] * (len(lst2)) for _ in range(len(lst1))]
for i in range(1, len(lst1)):
    for j in range(1, len(lst2)):
        if lst1[i] == lst2[j]:
            dp[i][j] = dp[i - 1][j - 1] + lst2[j]
        else:
            # dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
            # 그냥 냅다 비교하면 문자열 순서임 예를들면 ACB, CA >> CA가 우선
            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[-1][-1]), dp[-1][-1], sep="\n")

 

 

이 전에 했던 LCS 알고리즘을 한다.

 

역추적을 하려고 dp2 를 만들려고 했는데, 실패 해버렸다. 그래서 dp에 바로 알파벳을 저장하도록 했다.

전과 다른것은

else문에 그냥 max로 넣으면 

문자열길이 기준이 아니라 다르게 들어간다.