파이썬으로 문자열을 회문으로 분할하는 모든 방법의 수 구하기

문제 개요

하나의 문자열 s가 주어졌을 때, 분할된 각 부분 문자열이 모두 회문(palindrome)이 되도록 문자열을 나누는 방법이 몇 가지 있는지 구해야 합니다.

예를 들어 입력이 s = "xyyx"라면 출력은 3이 됩니다. 가능한 분할 방법은 다음과 같습니다.

• ["x", "yy", "x"]
• ["x", "y", "y", "x"]
• ["xyyx"]

접근 방법: 동적 계획법(DP)

이 문제는 동적 계획법을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

• n := 문자열 s의 길이
• table := 크기가 n + 1인 리스트를 만들고 0으로 초기화
• table[0] := 1 (빈 문자열을 분할하는 방법은 1가지로 정의)
• i를 0부터 n까지 반복:
  • j를 0부터 i-1까지 반복:
    • sub := s[j:i] (인덱스 j부터 i 직전까지의 부분 문자열)
    • 만약 sub가 회문이라면:
      • table[i] := table[i] + table[j]
• table의 마지막 요소를 반환

여기서 table[i]는 "앞에서 i번째 위치까지 잘랐을 때, 지금까지의 모든 조각이 회문이 되도록 만드는 분할 방법의 수"를 의미합니다. 즉, j부터 i까지 잘린 조각이 회문이라면, 그 앞부분(j까지)을 만드는 방법의 수(table[j])를 그대로 누적하는 방식입니다.

구현 예제

다음 코드를 통해 더 잘 이해해 보겠습니다.

class Solution:
   def solve(self, s):
      n = len(s)
      table = [1] + [0] * n
      for i in range(n + 1):
         for j in range(i):
            sub = s[j:i]
            if sub == sub[::-1]:
               table[i] += table[j]
      return table[-1]

ob = Solution()
s = "xyyx"
print(ob.solve(s))

입력

"xyyx"

출력

3

코드 설명

위 코드에서 회문 여부는 sub == sub[::-1] 비교를 통해 확인합니다. 파이썬의 슬라이싱 기법 [::-1]은 문자열을 뒤집은 결과를 반환하므로, 원본 문자열과 뒤집은 문자열이 같다면 그 문자열은 회문입니다.

시간 복잡도는 모든 (i, j) 쌍에 대해 부분 문자열을 추출하고 회문 검사를 수행하므로 O(n³)입니다. 문자열 길이가 크다면 팰린드롬 판별을 미리 계산해 두는 최적화(예: 중심 확장법 또는 DP 테이블 활용)를 적용하면 성능을 개선할 수 있습니다.