[백준] 5582번 공통 부분 문자열 파이썬 풀이

https://www.acmicpc.net/problem/5582

5582번: 공통 부분 문자열

---

1. 풀이

• DP 테이블을 활용하자

dp 테이블

아래 9251번 문제와 현재 5582번 문제는 비슷하지만, 확연한 차이점이 하나 있다. 9251번은 공통 부분 문자열 사이에 다른 문자열이 존재해도 괜찮았지만, 현재 5582번은 반드시 공통 서브 문자열이 서로 붙어 있어야 한다. 서브 문자열 사이에 다른 문자가 들어오면 안 된다.

[백준] 9251번 LCS 파이썬 풀이

따라서 dp 테이블에 값을 채울 때 행과 열이 서로 다른 문자면 0으로 둬야 한다. 같을 때만 초기화를 해주는데, 현재 위치가 (r, c)이면 (r - 1, c - 1)의 값 + 1로 초기화하면 된다.

이때 최장 길이를 나타내는 max_length 변수를 사용해서 (r, c) 값이 초기화될 때마다 기존 max_length 값과 새 (r, c) 값을 비교해서 더 큰 값으로 변경해주자. 그러면 dp 테이블이 모두 초기화된 후 max_length에 저장된 값이 바로 정답이 된다.

 

 

 

• 메모리 초과 유의! dp는 2차원 배열이 아니라, 1차원 배열로 사용하자

dp = [[0] * n for _ in range(m)]

사실 dp를 위와 같이 생성하고 활용하면 메모리 초과가 발생한다. 따라서 dp 테이블을 간소화해야 한다.

생각해 보면, 현재 (r, c) 값을 결정할 때 필요한 값은 (r - 1, c - 1)이다. 즉, 현재 행의 바로 이전 행만 필요하다. dp 테이블을 2차원 테이블로 구성해서 굳이 모든 값을 저장할 필요 없이, 1차원 배열로 바로 이전 행의 정보만 담고 있으면 되는 것이다.

 

 

 

2. 정답 코드

def get_longest_common_substring(x, y):
    x = " " + x
    y = " " + y
    n = len(x)
    m = len(y)

    max_length = 0
    dp = [0] * n  # 1차원 리스트

    for r in range(1, m):
        saved = [0] * n  # 현재 행의 정보를 담을 리스트
        for c in range(1, n):
            if x[c] == y[r]:
                saved[c] = dp[c - 1] + 1
                max_length = max(max_length, saved[c])
        dp = saved[:]  # 현재 행의 정보를 이전 행으로써 저장
    return max_length


str1 = input()
str2 = input()

print(get_longest_common_substring(str1, str2))