[백준/Python] 9252번 - LCS2

문제

백준 9252번 - LCS2

해결 과정

• 최장 공통 부분수열 길이를 구하고 찾기

• 최장 공통 부분수열 찾기

  1. LCS 배열의 가장 마지막 값에서 시작하며 결과값을 저장할 result 배열을 준비
  2. LCS[i - 1][j]와 LCS[i][j - 1] 중 현재 값과 같은 값을 찾습니다.
     2-1. 만약 같은 값이 있다면 해당 값으로 이동합니다.
     2-2. 만약 같은 값이 없다면 result배열에 해당 문자를 넣고 LCS[i -1][j - 1]로 이동합니다.
  3. 2번 과정을 반복하다가 0으로 이동하게 되면 종료합니다. result 배열의 역순이 LCS 입니다.

풀이

import sys

strA = sys.stdin.readline().strip()
strB = sys.stdin.readline().strip()

n = len(strA)
m = len(strB)

LCS = [[0] * (m+1) for _ in range(n+1)]

# 최대 공통 부분수열 길이 구하기
for i in range(1,n+1): 
  for j in range(1,m+1):
    if strA[i-1] == strB[j-1]:
      LCS[i][j] = LCS[i-1][j-1] + 1
    else:
      LCS[i][j] = max(LCS[i-1][j],LCS[i][j-1])


result = []

i = n 
j = m 
# 최대 공통 부분수열 찾기
while i > 0 and j > 0:
  if LCS[i][j] == LCS[i-1][j]:
    i -= 1
  elif LCS[i][j] == LCS[i][j-1]:
    j -= 1
  else:
    result.append(strA[i-1])
    i -= 1
    j -= 1

print(LCS[-1][-1])
for i in result[::-1]:
  print(i,end="")