[Python] G4_9252_LCS 2 🔎

https://www.acmicpc.net/problem/9252

문제

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

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

입력

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

출력

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

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

예제

코드

import sys
input = sys.stdin.readline
dp = ['']*1000
w1 = input().strip()
w2 = input().strip()
for i in range(len(w1)):
    temp = ''
    for j in range(len(w2)):
        # temp를 계속해서 LCS로 갱신해줌
        if len(temp) < len(dp[j]):
            temp = dp[j]
        # LCS에 문자열 하나가 더 붙는 경우
        elif w1[i] == w2[j]:
            dp[j] = temp + w2[j]
            
dp = list(set(dp)) # 중복 제거
dp = sorted(dp,key = lambda x : -len(x)) # 문자 길이를 기준으로 내림차순 정렬
LCS = dp[0]
if LCS:
    print(len(LCS))
    print(LCS)
else:
    print(0)

temp에는 LCS만이 들어가게 된다.

현재의 LCS가 들어간 상태에서, 또 공통 부분 문자열을 만나게 되면 추가해서 넣어준다.

# LCS에 문자열 하나가 더 붙는 경우
elif w1[i] == w2[j]:
	dp[j] = temp + w2[j]

이와 같은 작업을 모든 부분 문자열에 대해 실행한다.

dp를 가지고 최종적인 LCS를 구한다.

dp는 1000개의 리스트이기에, 중복을 제거해주기 위해 집합을 활용한다.

dp = list(set(dp)) # 중복 제거

이 중에서 가장 긴 공통 부분 문자열, 즉 LCS를 찾아주기 위해서 정렬한다.

dp = sorted(dp,key = lambda x : -len(x)) # 문자 길이를 기준으로 내림차순 정렬

• dp[0] 에는 가장 긴 문자열이 있게 되고, 이는 LCS에 해당한다.

LCS를 길이와 함께 출력해준다.

• 만약 LCS가 비어있다면, 0만 출력한다.

느낀 점 & 배운 점

1. LCS 1 문제를 풀고, 문자열도 저장해주기 위해서 dp안에 길이가 아닌 문자열 자체를 저장해주며 해결했다.

2. 입력이 많지 않은 경우에서는 이와 같이 충분히 풀 수 있을 것 같다!