[BOJ] Q9252 LCS2

[BOJ] Q9252 LCS2

Question

Language: Python

Difficulty: Gold 4

해당 문제는 LCS 유형의 문제이다.

LCS 문제는 가장 긴 공통 부분 수열을 구하는 문제로, 전형적인 DP문제이다.

문자열 1, 문자열 2에 대해 이중-for문을 활용해서 서로 비교해가는데, 만약 서로 같은 경우, 이는 공통된 부분 수열의 길이가 증가하는 것을 의미하기 때문에, 이전 최대 길이에서 하나 만큼 추가 시켜준다.

만약 서로 다른 경우, 기존 까지의 최대 부분 수열 길이로 초기화한다.

algorithm

if str2[i-1]==str1[j-1]:
    di[i][j]=di[i-1][j-1]+str2[i-1]
else:
    di[i][j]=max(di[i-1][j],di[i][j-1])

하지만, 지금은 LCS 문자열을 구해야하므로, +1을 해주는 것이 아닌 문자를 추가해준다.

아니면, 기존의 LCS 알고리즘을 통해서 DI 배열을 완성 시킨 다음, 사선으로 이동하는 부분(문자열이 증가하는 부분)에서 LCS를 늘려나가는 방법도 있다.

Solution 1

from collections import deque
def solution():
    str1_length=len(str1)
    str2_length=len(str2)

    di=[[""] * (str1_length+1) for _ in range(str2_length+1)]
    lcs=[]
    for i in range(1,str2_length+1):
        for j in range(1,str1_length+1):
            if str2[i-1]==str1[j-1]:
                di[i][j]=di[i-1][j-1]+str2[i-1]
            else:
                if len(di[i-1][j]) < len(di[i][j-1]):
                    di[i][j]=di[i][j-1]
                else:
                    di[i][j]=di[i-1][j]
    print(len(di[-1][-1]))
    print((di[-1][-1]))

if __name__ == "__main__":
    str1=list(input().strip())
    str2=list(input().strip())
    
    solution()

Solution 2

def solution():
    str1_length=len(str1)
    str2_length=len(str2)

    di=[[0] * (str1_length+1) for _ in range(str2_length+1)]
    lcs=[]
    for i in range(1,str2_length+1):
        for j in range(1,str1_length+1):
            if str2[i-1]==str1[j-1]:
                di[i][j]=di[i-1][j-1]+1
            else:
                di[i][j]=max(di[i-1][j],di[i][j-1])
 
    row=str2_length
    col=str1_length

    lcs=""
    while di[row][col] !=0:
        if di[row-1][col]==di[row][col]:
            row-=1
        elif di[row][col-1]==di[row][col]:
            col-=1
        else:
            lcs=str1[col-1]+lcs
            row-=1
            col-=1

    print(len(lcs))
    print(lcs)

if __name__ == "__main__":
    str1,str2="",""

    with open("input9252.txt","r") as file:
        str1=list(file.readline().strip())
        str2=list(file.readline().strip())
    
    print(str1,str2)
    
    solution()