[Baekjoon] 5582번 : 공통 부분 문자열 (Python, 문자열, DP)

[Baekjoon] 5582번 : 공통 부분 문자열 (Python, 문자열, DP)

 

목차

 

 

 

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

5582번: 공통 부분 문자열

 

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1  - 코드 길이 359B

 

당연하겠지만 $O(N^3)$에 해당하는 코드가 시간 초과가 안 날 수 없다.

직관적인 해결법 말고 다른 해결법이 필요하다.

 

import sys
input = sys.stdin.readline

s = list(input().rstrip())
o = list(input().rstrip())
ans = 0

for i in range(len(s)):
    for j in range(len(o)):
        k = 1
        while 1:
            if s[i:i+k] == o[j:j+k] and i+k <= len(s) and j+k <= len(o):
                k += 1
            else:
                break
        ans = max(ans, k-1)
print(ans)

 

시간 초과 - 방법 2 - 메모리 240460KB / 시간 456ms / 코드 길이 284B (PyPy3 통과)

 

DP를 이용한 방법으로 memorization을 생각한 방법이다.

 

	NULL	A	B	R	A	C	A	D	A
NULL	0	0	0	0	0	0	0	0	0
E	0	0	0	0	0	0	0	0	0
C	0	0	0	0	0	0+1=1	0	0	0
A	0	0+1=1	0	0	0+1=1	0	1+1=2	0	0+1=1
D	0	0	0	0	0	0	0	2+1=3	0
A	0	0+1=1	0	0	0+1=1	0	0+1=1	0	3+1=4
D	0	0	0	0	0	0	0	1+1=2	0
A	0	0+1=1	0	0	0+1=1	0	0+1=1	0	2+1=3
D	0	0	0	0	0	0	0	1+1=2	0

 

DP를 통해 $O(N^2)$만으로 문제를 해결할 수 있다.

 

import sys
input = sys.stdin.readline

s = input().rstrip()
o = input().rstrip()
dp = [[0]*(len(s)+1) for _ in range(len(o)+1)]
for i in range(1, len(o)+1):
    for j in range(1, len(s)+1):
        if o[i-1] == s[j-1]:
            dp[i][j] = dp[i-1][j-1] + 1

print(max(map(max, dp)))

 

방법 3 - 메모리 30840KB / 시간 4720ms / 코드 길이 269B 

 

방법 2를 자세히 확인하면 결국 이전 list와 이후 list 간의 내용을 확인하는 것을 알 수 있다.

이 점을 통해 간소화를 한다면 아래와 같이 코드를 수정할 수 있다. 

 

A = input()
B = input()

LA = len(A)
LB = len(B)

prev = [0] * (LB + 1)
ans = 0

for i in range(LA):
    tmp = [0] * (LB + 1)
    for j in range(LB):
        if A[i] == B[j]:
            tmp[j + 1] = prev[j] + 1
    ans = max(ans, max(tmp))
    prev = tmp[:]
print(ans)