[BOJ][python] 5582_공통부분문자열

문제

# 예제 입력
ABRACADABRA
ECADADABRBCRDARA

# 예제 출력
5

문제 보러가기 : 5582번: 공통 부분 문자열

풀이 :

• Key point (생략가능)
  • 공통 부분 문자열이 아니라 공통 부분 문자열의 길이가 필요하다
  • DP 를 활용하자
• Logic :
  • 문자열 s1 의 한 문자당 문자열 s2의 문자들과 같은 것이 있는지 확인이 필요하다. → 이차원 배열 dp 를 만들자

    dp=[[0]*(len(s2)+1) for _ in range(len(s1)+1)]

  • dp[i][j] 에는 문자열 s1[i] 문자열 s2[j] 에 있는 값이 같은 경우에 dp[i-1][j-1]에 1을 증가시킨 값이 들어가게된다.
    • 두 문자열을 전부 다 확인해가면서 공통 부분 문자열을 찾는 과정에서 이전 값들에 대한 확인이 계속적으로 필요하다. 이때 이전 값들을 매번 다시 확인할 필요 없이 dp에 저장해주면 된다. 이러한 로직은 dynamic programming 알고리즘을 따른다고 볼 수 있다.
    • 쉬운 예로 apple 과 applepie가 있다고 해보자. 이때 문자 e 에 대해서 같은지 체크할때 연속해서 같은 값이 나왔는지 확인하기 위해 문자 l 이 같은지 확인이 필요하다. 또 문자 l 이전에 연속해서 같은 값이 나왔는지 확인하기 위해 이전 값 을 확인하게 된다.

코드 :

import sys
input = sys.stdin.readline

'''
input : ABRACADABRA
ECADADABRBCRDARA
output : 5'''

# s1=list(input().rstrip())
# s2=list(input().rstrip())

s1=input()
s2=input()
max_str_len=0

dp=[[0]*(len(s2)+1) for _ in range(len(s1)+1)]

for i in range(1,len(s1)+1):
    for j in range(1,len(s2)+1):
        if (s1[i-1]==s2[j-1]):
            dp[i][j]=dp[i-1][j-1]+1
            max_str_len=max(dp[i][j],max_str_len)
print(max_str_len)

---

느낀점 :

공통 부분 문자열이 아니라 공통 부분 문자열의 길이가 필요한 것 이였는데 어떻게든 최대 공통 부분 문자열을 찾아서 그 문자열의 길이를 구할려고 했던 점이 문제를 못 푼 요인이였다.

정답은 나왔지만 계속해서 시간초과, 메모리 초과 가 나왔다.

이럴때에는 문제 접근 방식에 대해서 새롭게 고민해 볼 필요가 있는 것 같다.