백준 번 바로가기

첫 번째 풀이

# 입력
import sys
read = sys.stdin.readline

A, B = read().strip(), read().strip()
n, m = len(A), len(B)
LCS = [[0] * (m + 1) for _ in range(n + 1)]
LCS2 = [[''] * (m + 1) for _ in range(n + 1)]

# 처리 - LCS 알고리즘 이용
for i in range(1, n + 1):
  for j in range(1, m + 1):
    if A[i - 1] == B[j - 1]:
      LCS[i][j] = LCS[i - 1][j - 1] + 1
      LCS2[i][j] = LCS2[i - 1][j - 1] + A[i-1]
    else:
      LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])
      if LCS[i-1][j] > LCS[i][j-1]:
        LCS2[i][j] = LCS2[i-1][j]
      else:
        LCS2[i][j] = LCS2[i][j-1]

print(LCS[n][m])
print(LCS2[n][m])

두 번째 풀이

# 입력
import sys

read = sys.stdin.readline

A, B = read().strip(), read().strip()
n, m = len(A), len(B)
LCS = [[0] * (m + 1) for _ in range(n + 1)]

# 처리 - LCS 알고리즘 이용
for i in range(1, n + 1):
  for j in range(1, m + 1):
    if A[i - 1] == B[j - 1]:
      LCS[i][j] = LCS[i - 1][j - 1] + 1
    else:
      LCS[i][j] = max(LCS[i - 1][j], LCS[i][j - 1])

print(LCS[n][m])

ans = ''
x, y = n, m
while x > 0 and y > 0:
  if LCS[x][y] == LCS[x - 1][y]:
    x -= 1
  elif LCS[x][y] == LCS[x][y - 1]:
    y -= 1
  else:
    ans += A[x-1]
    x -= 1
    y -= 1

print(ans[::-1])

CODE REVIEW

  1. 백준 9251번 - LCS의 연장선 격인 문제.
  2. 첫 번째 풀이의 경우 시간초과 에러가 발생했는데, string을 저장하는 과정 자체가 시간이 오래 소요되는 것으로 판단된다.
  3. 두 번째 풀이에서는 LCS2 matrix을 사용하지 않고, LCS을 그대로 사용하면서 역추적 해나가는 방식을 택했다.
    • 역추적 해가면서 대각선으로 움직이는 시점의 문자를 더해가며 문자열을 찾아낼 수 있다.