[BOJ] 백준 5582번 문제 풀이 (Python)

1. 풀이

두 문자열에 모두 포함 된 부분 문자열 중 가장 긴 것의 길이를 구하는 문제이다. Python 내장 함수인 find와 index의 경우 time complexity가 $O(n)$이기 때문에 find와 index를 쓰지 않고 문제를 풀려고 노력했다.

1.1. 첫번째 풀이

import sys
def input(): return sys.stdin.readline().rstrip()

s1,s2 = input(), input()
subs = set()
for i in range(len(s1)):
    for j in range(i+1,len(s1)):
        subs.add(s1[i:j])
max_len = 0
for i in range(len(s2)):
    for j in range(len(s2)):
        if s2[i:j] in subs and max_len < j-i:
            max_len = j-i
print(max_len)

처음에는 문자열 1이 가진 모든 부분 문자열을 set에 저장한 뒤 문자열 2가 가진 부분 문자열과 비교해서 최대 길이를 출력했다. 메모리 초과가 발생해 사용할 수 없었는데 아마도 최대 4000길이인 문자열의 모든 부분 문자열을 저장해서 제한 조건을 초과하는 것 같았다.

1.2. 두번째 풀이

최종적으로 2차원 배열에 공통으로 존재하는 부분 문자열의 길이를 저장하는 방식을 이용해 문제를 풀었다.

• 첫번째로 입력받는 문자열을 $s1$, 두번째로 입력받는 문자열을 $s2$ 하자
• $subs\text{[i][j]}$: 해당 위치의 문자를 포함한 공통 부분 문자열의 길이
  • $1 + subs[\text{i-1}][\text{j-1}] \,\,\,\,\, \text{if s1[i] = s2[j]}$
  • $0 \,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\,\, \text{if s1[i]} \ne \text{s2[j]}$

s1의 i번째 문자와 s2의 j번째 문자가 같은 경우 해당 문자를 포함한 공통 부분 문자열의 길이를 계속 갱신하는 방식이다. 최종 코드는 아래와 같다.

import sys
def input(): return sys.stdin.readline().rstrip()

s1, s2 = input(), input()
subs = [[0] * len(s2) for _ in range(len(s1))]

for i in range(len(s1)):
    for j in range(len(s2)):
        if s1[i] == s2[j]:
            subs[i][j] = 1 
            if i-1 >= 0 and j-1 >= 0:
                subs[i][j] += subs[i-1][j-1]
            
print(max([max(arr) for arr in subs]))

문자열에 DP를 적용하는 알고리즘 중에 비슷한 문제로 편집거리 알고리즘이 존재한다. 백준 15483번에 등록이 되어있으니 해당 문제를 같이 풀어보는 것을 추천한다.