[BOJ] 9252 - LCS 2 (Python)

 

 

아이디어

 

동적 계획법으로 두 문자열의 최장 공통 부분 열을 찾아 나간다.

 

 

풀이

 

두 문자열을 각각 S1, S2에 저장하고, 그 길이를 각각 N1, N2에 저장한다.

인덱스 접근의 편리를 위해 1만큼의 여유를 둬서 빈 문자열로 채워진 N2+1 길이의 리스트 dp를 생성한다.

메모리 절약을 위해 dp를 2차원 리스트로 만들지 않고, 현재 행에 대한 처리는 lcs에 하고 dp를 대체해 나간다.

lcs[i+1][j+1]에는 S1의 i 번째 문자, S2의 j 번째 문자의 최장 공통 부분 열을 저장한다.

 

S1, S2의 문자가 같을 때 해당 문자들 이전까지의 최장 공통 부분 열에 해당 문자를 더한 문자열을 저장하고,

그렇지 않으면 현재까지 저장된 부분 열 중 더 긴 부분 열의 문자열을 저장해 나간다.

 

def solution():
    S1, S2 = input(), input()
    N1, N2 = map(len, [S1, S2])
    dp = ['']*(N2+1)
    for i in range(N1):
        lcs = ['']*(N2+1)
        for j in range(N2):
            if S1[i] == S2[j]:
                lcs[j+1] = dp[j]+S1[i]
            else:
                if len(dp[j+1]) > len(lcs[j]):
                    lcs[j+1] = dp[j+1]
                else:
                    lcs[j+1] = lcs[j]
        dp = lcs
    print(len(dp[-1]))
    if dp[-1]:
        print(dp[-1])

solution()

 

 

dp를 2차원 리스트로 사용하는 코드에서는 메모리 사용량이 약 13.1배, 시간은 약 2.4배로 늘었다.

# 메모리를 더 많이 사용하고 더 느린 코드
dp = [['']*(N2+1) for _ in range(N1+1)]
for i in range(N1):
    for j in range(N2):
        if S1[i] == S2[j]:
            dp[i+1][j+1] = dp[i][j]+S1[i]
        else:
            if len(dp[i][j+1]) > len(dp[i+1][j]):
                dp[i+1][j+1] = dp[i][j+1]
            else:
                dp[i+1][j+1] = dp[i+1][j]