문자열 S가 주어졌을 때, 이 문자열에서 가장 긴 회문(palindrome) 부분 문자열의 길이를 구하는 문제입니다. 문자열 S의 최대 길이는 1000이라고 가정합니다. 예를 들어 문자열이 "BABAC"라면 가장 긴 회문 부분 문자열은 "BAB"이며, 그 길이는 3입니다.
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심은 이미 계산한 짧은 부분 문자열의 회문 여부를 재활용하여, 점점 더 긴 부분 문자열을 검사하는 것입니다.
알고리즘 접근 방법
문자열 길이와 같은 크기의 정사각형 DP 행렬을 정의하고 모든 값을 False로 초기화합니다.
주 대각선 요소를 True로 설정합니다. 즉, i가 0부터 n-1까지일 때 DP[i][i] = True로 지정합니다. (길이 1인 문자는 항상 회문입니다.)
start 변수를 0으로 초기화합니다.
부분 문자열의 길이 l을 2부터 문자열 길이까지 늘려가며 반복합니다.
시작 인덱스 i를 0부터 len(S) − l + 1 범위에서 반복하면서 각 부분 문자열을 검사합니다.
끝 인덱스를 end := i + l로 계산합니다.
l이 2인 경우(길이 2의 부분 문자열): S[i] == S[end − 1]이라면 앞뒤 글자가 같으므로 DP[i][end − 1] = True로 설정하고, max_len := l, start := i로 갱신합니다.
그 외의 경우: S[i] == S[end − 1]이면서 내부 부분 문자열도 회문(DP[i + 1][end − 2] == True)일 때만 DP[i][end − 1] = True로 설정하고, max_len := l, start := i로 갱신합니다.
모든 반복이 끝나면 max_len을 반환합니다.
다음 예제 코드를 통해 더 자세히 살펴보겠습니다.
예제 코드
class Solution(object):
def solve(self, s):
n = len(s)
dp = [[False for i in range(n)] for i in range(n)]
for i in range(n):
dp[i][i] = True
max_length = 1
start = 0
for l in range(2, n + 1):
for i in range(n - l + 1):
end = i + l
if l == 2:
if s[i] == s[end - 1]:
dp[i][end - 1] = True
max_length = l
start = i
else:
if s[i] == s[end - 1] and dp[i + 1][end - 2]:
dp[i][end - 1] = True
max_length = l
start = i
return max_length
ob = Solution()
print(ob.solve('ABBABBC'))입력
"ABBABBC"
출력
5
"ABBABBC"에서 가장 긴 회문 부분 문자열은 "BBABB"이며, 그 길이는 5입니다. 위 코드에서 DP[i][j]는 s[i..j] 구간이 회문인지 여부를 저장하며, 길이가 짧은 부분 문자열부터 차례대로 결과를 채워 나가는 바텀업(bottom-up) 방식으로 동작합니다.
복잡도 분석
두 개의 중첩 반복문을 사용하므로 시간 복잡도는 O(n²)이며, DP 테이블을 저장하기 위한 공간 복잡도 또한 O(n²)입니다. 문자열 길이가 1000 이하인 조건에서는 충분히 빠른 속도로 동작합니다.