문자열 s가 주어졌을 때, 이 문자열이 회문(palindrome)이 되도록 만들기 위해 삽입해야 하는 최소 문자 수를 구하는 문제입니다.
예를 들어 입력이 s = "mad"라면, "am"을 삽입하여 "madam"을 만들 수 있으므로 정답은 2가 됩니다.
접근 방법
이 문제는 재귀적 동적 계획법(Dynamic Programming)으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 두 포인터 i(시작)와 j(끝)를 사용해 부분 문자열을 탐색합니다.
- s[i]와 s[j]가 같다면 두 문자는 이미 회문의 양쪽 끝 역할을 할 수 있으므로, 안쪽 부분인 dp(i + 1, j - 1)만 확인하면 됩니다.
- s[i]와 s[j]가 다르다면 왼쪽 또는 오른쪽에 새 문자를 삽입하는 두 가지 선택지 중 최솟값을 취하고 1을 더합니다.
알고리즘 단계
- dp(i, j) 함수를 정의합니다.
- i >= j이면 0을 반환합니다. (길이가 0 또는 1인 부분 문자열은 이미 회문)
- s[i] == s[j]이면 dp(i + 1, j - 1)을 반환합니다.
- 그렇지 않으면 min(dp(i + 1, j), dp(i, j - 1))에 1을 더해 반환합니다.
- 메인 메서드에서는 dp(0, len(s) - 1)을 반환합니다.
아래 구현 예제를 통해 더 잘 이해해 보겠습니다.
구현 예제
class Solution:
def solve(self, s):
def dp(i, j):
if i >= j:
return 0
if s[i] == s[j]:
return dp(i + 1, j - 1)
else:
return min(dp(i + 1, j), dp(i, j - 1)) + 1
return dp(0, len(s) - 1)
ob = Solution()
s = "mad"
print(ob.solve(s))
입력
s = "mad"
출력
2
복잡도 분석 및 최적화 팁
위 순수 재귀 풀이의 시간 복잡도는 지수적으로 증가할 수 있습니다. functools.lru_cache 같은 메모이제이션을 적용하면 시간 복잡도를 O(n²)으로 줄일 수 있으며, 공간 복잡도 역시 DP 테이블 크기에 비례해 O(n²)이 됩니다.
또한 이 문제는 최장 회문 부분 수열(Longest Palindromic Subsequence, LPS)과 밀접한 관련이 있습니다. 문자열 길이 n에서 LPS 길이를 뺀 값, 즉 n − LPS(s)가 곧 필요한 최소 삽입 문자 수와 같다는 성질을 활용하면 다른 방식으로도 문제를 해결할 수 있습니다.