BOJ 9252(python) : LCS 2

문제 링크

모두의 부분 수열이 되는 수열 중 가장 긴 것을 찾는 문제이다.

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

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

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

예제 입력
ACAYKP
CAPCAK

예제 출력
4
ACAK

---

Solution

풀이 유투브

시간복잡도 O(N**2), N은 최대1,000 총 1,000,000번의 계산

최대 문자열 길이 구하기는 기존 LCS문제와 동일

for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
	#이중 포문으로 서로같은 문자일때 
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
            continue
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

---

최대 문자열 출력은?

dp의 끝부터 계산하며

if a[i] == b[j] 이면 리스트에 a[i]를 담고, dp[i-1][j-1]으로 이동

else dp[i-1][j] 또는 dp[i][j-1] 왼쪽 위로 전진하면서 dp[i][j]와 동일한 값으로 이동한다.

i 또는 j인덱스가 0에 도달하면 종료한다.

i = len(a)-1
j = len(b)-1

while i >=0 and j>=0:
    if b[j] == a[i]:
        strlist.append(b[j])
        j-=1
        i-=1
        continue
    if dp[i+1][j+1] == dp[i][j+1]:
        i-=1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j-=1

---

전체소스

import sys

a = str(sys.stdin.readline().replace('\n',''))
b = str(sys.stdin.readline().replace('\n',''))
strlist = list()

#dp Table 크기를 a,b사이즈보다 1씩 크게 생성
dp = [[0] * (len(b)+1) for i in range(len(a)+1)]

for i in range(1,len(a)+1):
    for j in range(1,len(b)+1):
        if a[i-1] == b[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1
            continue
        dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
print(dp[len(a)][len(b)]) #최대 길이 출력

if dp[len(a)][len(b)]==0:
    quit()
i = len(a)-1
j = len(b)-1

while i >=0 and j>=0:
    if b[j] == a[i]:
        strlist.append(b[j])
        j-=1
        i-=1
        continue
    if dp[i+1][j+1] == dp[i][j+1]:
        i-=1
    elif dp[i+1][j+1] == dp[i+1][j]:
        j-=1
strlist.reverse()
for i in strlist:
    print(i,end='')