[BOJ] 9252. LCS 2 (Python)

9252번: LCS 2

 

오랜만에 코테 풀기!

 

LCS란 최장 공통 부분 수열을 의미한다.

두 개의 문자열이 있을 때, 최장 공통 부분 수열이란 다음과 같다.

 

ACAYKP

 

CAPCAK

---------> ACAK

 

그렇다면 어떻게 최장 공통 부분 수열을 구할 수 있을까?

 

위 예시를 통해 최장 공통 부분 수열을 구하는 법을 살펴보자!

 

우선 아래와 같은 배열이 존재한다고 가정하자.행에 있는 문자를 기준으로 열에 해당 문자가 존재하는지 체크하고, 존재한다면 기존 길이 + 1을 해주면 된다.

 

예를 들어 우선 행의 첫 번째 문자 C를 기준으로 살펴보자.

행에 있는 문자 C가 열에서 처음으로 만나는 부분은 아래와 같다.

 

 

공통적인 문자를 찾았으면 이전에 내가 알고 있던 최장 공통 부분 수열의 길이 + 1을 해준 값으로 업데이트를 해주면된다.

 

만약 같은 문자가 아닌 경우에는 어떻게 해야할까?

그때는 이전에 내가 알고 있는 공통 부분 수열의 길이 중 가장 긴 값으로 채워넣으면 된다.

이때 알고 있는 공통 부분 수열의 길이 중 가장 긴 값은 [i-1][j], [i][j-1] 중 max 값이 된다.

 

우리는 매 순간 최장 공통 부분 수열만 알면 되므로 최장일때의 기록만을 갖고 있으면 되기 때문이다!

 

이런 식으로 문자열을 모두 비교해보면 아래와 같은 배열을 얻을 수 있다! (잘 이해가 안가면 한 번 직접 계산해서 비교해보길 추천!)

 

 

매 순간 최장일때의 기록만을 행렬에 저장하였으므로 행렬의 맨 마지막 행, 맨 마지막 열의 값이 바로 최장 공통 부분 수열의 길이가 된다!

 

 

그런데 여기서!

최장 공통 부분 수열의 길이만 찾으라고 하면 여기서 끝나면 된다.

하지만 문제에서 원하는 것은 최장 공통 부분 수열이 어떻게 생겼는지까지이다.

 

어떻게 효과적으로 구할 수 있을까?

 

행렬에서 숫자를 따라 가는 방법도 있지만 가장 간단한 방법은 애초에 최장 공통 부분 수열을 계산할 때 길이가 아니라 최장 공통 부분 수열 자체를 저장하는 것이다!

(* 최장 공통 부분 수열 중 아무거나 하나 출력하면 되므로 동일한 길이일때는 [i-1][j], [i][j-1] 중 뭘 가져오든 상관 X

 

 

 

 

코드 구현은 아래와 같다.

 

str1 = [0] + list(input())
str2 = [0] + list(input())

len_1 = len(str1)
len_2 = len(str2)

array = [['' for _ in range(len_1)] for _ in range(len_2)]

for i in range(1, len_2) :
    for j in range(1, len_1) :
        if str1[j] == str2[i] :
            array[i][j] = array[i-1][j-1] + str1[j]
        else :
            if len(array[i][j-1]) > len(array[i-1][j]) :
                array[i][j] = array[i][j-1]
            else : 
                array[i][j] = array[i-1][j]

answer = len(array[-1][-1])
print(answer)
if answer != 0 :
    print(array[-1][-1])