파이썬으로 문자열이 세 개의 회문으로 나누어지는지 확인하는 방법

문제 이해하기

문자열 s가 하나 주어졌을 때, 이 문자열을 세 개의 회문(palindrome) 부분 문자열로 나눌 수 있는지 확인해야 합니다.

예를 들어 입력이 s = "levelpopracecar"라면, "level", "pop", "racecar" 세 부분으로 나눌 수 있고 각각이 모두 회문이므로 결과는 True가 됩니다.

접근 방법 (알고리즘)

이 문제는 동적 계획법(DP)을 활용해 효율적으로 해결할 수 있습니다. 먼저 모든 부분 문자열에 대한 회문 여부를 미리 계산해 둔 뒤, 세 구간으로 나누는 모든 경우를 확인하는 방식입니다.

• n := 문자열 s의 길이
• dp := n × n 크기의 2차원 행렬을 만들고 모든 값을 False로 초기화
• i를 n-1부터 0까지 1씩 감소시키며 반복:
  • j를 0부터 n-1까지 반복:
    • i >= j이면 dp[i][j] := True (길이가 1 이하인 부분 문자열은 항상 회문)
    • 그렇지 않고 s[i]와 s[j]가 같으면 dp[i][j] := dp[i+1][j-1]
• i를 1부터 n-1까지 반복:
  • j를 i+1부터 n-1까지 반복:
    • dp[0][i-1], dp[i][j-1], dp[j][n-1]이 모두 True이면 True 반환
• 모든 경우를 확인한 후에도 찾지 못하면 False 반환

예제 코드

아래 파이썬 구현을 통해 더 잘 이해해 보겠습니다.

def solve(s):
   n = len(s)

   dp = [[False] * n for _ in range(n)]
   for i in range(n-1, -1, -1):
      for j in range(n):
         if i >= j:
            dp[i][j] = True
         elif s[i] == s[j]:
            dp[i][j] = dp[i+1][j-1]
   for i in range(1, n):
      for j in range(i+1, n):
         if dp[0][i-1] and dp[i][j-1] and dp[j][n-1]:
            return True
   return False

s = "levelpopracecar"
print(solve(s))

동작 원리 설명

dp[i][j]는 부분 문자열 s[i..j]가 회문인지 여부를 저장하는 테이블입니다. 양 끝 문자가 같고, 그 안쪽 구간(dp[i+1][j-1])도 회문이라면 해당 구간 역시 회문이 됩니다. 이렇게 완성된 DP 테이블을 이용해 첫 번째 구간 [0, i-1], 두 번째 구간 [i, j-1], 세 번째 구간 [j, n-1]이 모두 회문인 조합이 존재하는지 검사합니다.

이 알고리즘의 시간 복잡도는 O(n²), 공간 복잡도 역시 O(n²)입니다.

입력

"levelpopracecar"

출력

True