[BOJ] #9252 LCS 2

LCS 2

백준 #9252

---

📌 문제

예제 입력

ACAYKP
CAPCAK

예제 출력

4
ACAK

---

📌 풀이

Logic

• #9251에서 기능 추가
• 가장 긴 LCS를 역으로 추적하는 방식
  • str1, str2의 길이 i, j가 0이 될 때 까지,,
  • 각 str의 문자를 비교하며 LCS에 추가

# 변수명
str1, str2 : 비교할 두 문자열
i, j : 두 문자열의 길이

Python

import sys

str1 = sys.stdin.readline().strip()
str2 = sys.stdin.readline().strip()

dp = [[0] * (len(str2) + 1) for _ in range(len(str1) + 1)]

for i in range(1, len(str1) + 1):
    for j in range(1, len(str2) + 1):
        if (str1[i - 1] == str2[j - 1]):
            dp[i][j] = dp[i - 1][j - 1] + 1

        else:
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])  

print(dp[-1][-1])

LCS = []
i, j = len(str1), len(str2)

while (i > 0 and j > 0):
    if (str1[i - 1] == str2[j - 1]):
        LCS.append(str1[i - 1])
        i -= 1
        j -= 1

    elif (dp[i - 1][j] > dp[i][j - 1]):
        i -= 1

    else:
        j -= 1

if (dp[-1][-1] > 0):
    print(''.join(reversed(LCS)))

---

✏️ 새로운 내용

-

---

📚 회고

💡 #9251의 연장선

• LCS를 처음부터 찾으면서 길이까지 파악하려고 하니, 너무 꼬이는 것 같았다.
• 기존의 코드를 바탕으로 LCS를 빠르게 다시 역으로 찾는 것이 훨씬 효율적이었다.