C++로 문자열을 회문으로 분할하는 최소 횟수 계산하기

문제 개요

소문자로만 이루어진 문자열 s가 주어졌을 때, 각 부분 문자열이 모두 회문(palindrome)이 되도록 문자열을 최소한의 조각으로 분할하고, 그 결과 얻어지는 문자열의 개수를 구하는 프로그램을 작성해야 합니다.

예를 들어 입력이 s = "levelracecar"라면, "level"과 "racecar"라는 두 개의 회문으로 나눌 수 있으므로 출력은 2가 됩니다.

해결 접근 방법

이 문제는 동적 계획법(Dynamic Programming)을 활용하여 해결할 수 있습니다. 문자열의 끝에서부터 앞쪽으로 탐색하면서, 각 위치 i에서 시작했을 때 필요한 최소 분할 횟수를 차례대로 계산합니다.

알고리즘 단계

• n := 문자열 A의 길이로 설정합니다.
• 크기가 (n + 1)인 배열 result를 정의합니다.
• result[n] := -1로 초기화합니다.
• i := n - 1부터 시작하여 i >= 0일 때까지 i를 1씩 감소시키며 반복합니다.
  • result[i] := n - i - 1로 초기화합니다.
  • j := i부터 j < n일 때까지 j를 1씩 증가시키며 반복합니다.
    • A의 i번째부터 j번째까지의 부분 문자열이 회문이라면:
      • result[i] := result[i]와 (1 + result[j + 1]) 중 최솟값으로 갱신합니다.
• 최종적으로 result[0] + 1을 반환합니다. (+1은 분할된 조각의 개수를 의미합니다.)

C++ 구현 예제

아래 코드를 통해 더 자세히 이해해 보겠습니다.

#include <bits/stdc++.h>
using namespace std;
class Solution {
   public:
   bool isPalindrome(string A) {
      int left = 0;
      int right = A.size() - 1;
      while (left < right) {
         if (A[left] != A[right]) {
            return 0;
         }
         left++;
         right--;
      }
      return 1;
   }
   int solve(string A) {
      int n = A.size();
      vector<int> result(n + 1);
      result[n] = -1;
      for (int i = n - 1; i >= 0; i--) {
         result[i] = n - i - 1;
         for (int j = i; j < n; j++) {
            if (isPalindrome(A.substr(i, j - i + 1))) {
               result[i] = min(result[i], 1 + result[j + 1]);
            }
         }
      }
      return result[0] + 1;
   }
};
int solve(string s) {
   return (new Solution())->solve(s);
}
int main(){
   string s = "levelracecar";
   cout << solve(s);
}

입력

"levelracecar"

출력

2

복잡도 분석

모든 시작 위치 i와 끝 위치 j의 조합을 검사하고, 각 부분 문자열에 대해 회문 여부를 확인하므로 시간 복잡도는 O(n³)입니다. 공간 복잡도는 DP 배열을 저장하기 위해 O(n)입니다. 만약 회문 판정을 미리 계산해 두는 2차원 테이블을 사용하면 시간 복잡도를 O(n²)까지 줄일 수 있습니다.