문제 정의
숫자(정수) 문자만으로 구성된 문자열이 주어집니다. 한 번의 단계에서 회문(palindrome)인 부분 문자열을 삭제할 수 있을 때, 이 문자열 전체를 최소 단계로 모두 제거하는 방법을 구하는 것이 목표입니다. 부분 문자열을 삭제한 후에는 남은 앞뒤 부분들이 서로 연결되어 하나의 문자열이 됩니다.
예시
입력 문자열이 3441213이라면 최소 2단계가 필요합니다.
- 먼저 문자열에서 121을 제거합니다. 남은 문자열은 3443입니다.
- 남은 문자열 3443 자체가 회문이므로 한 번에 모두 제거합니다.
알고리즘
이 문제는 동적 계획법(Dynamic Programming)으로 효율적으로 해결할 수 있습니다.
1. dp[i][j]를 부분 문자열 s[i, j]를 삭제하는 데 필요한 단계 수로 정의한다.
2. 각 문자는 혼자 삭제되거나 어떤 부분 문자열의 일부로 삭제된다.
첫 번째 경우에는 해당 문자 하나를 삭제하고 하위 문제 (i+1, j)를 호출한다.
3. 두 번째 경우에는 오른쪽 구간에서 현재 문자와 같은 문자가 나타나는
모든 위치를 탐색한다. 그중 하나의 인덱스를 K라 하면,
문제는 두 개의 하위 문제 (i+1, K-1)와 (K+1, j)로 분할된다.
4. 하위 문제 (i+1, K-1)에 도달할 수 있는 이유는 양 끝의 같은 문자를
먼저 삭제한 뒤 가운데 부분 문자열에 대해 재귀적으로 처리할 수 있기 때문이다.
5. 처음 두 문자가 서로 같은 경우는 별도로 처리하며,
이때는 곧바로 하위 문제 (i+2, j)로 축소할 수 있다.
C++ 구현 예제
#include <bits/stdc++.h>
using namespace std;
int getMinRequiredSteps(string str) {
int n = str.length();
int dp[n + 1][n + 1];
for (int i = 0; i <= n; i++) {
for (int j = 0; j <= n; j++) {
dp[i][j] = 0;
}
}
for (int len = 1; len <= n; len++) {
for (int i = 0, j = len - 1; j < n; i++, j++) {
if (len == 1)
dp[i][j] = 1;
else {
dp[i][j] = 1 + dp[i + 1][j];
if (str[i] == str[i + 1]) {
dp[i][j] = min(1 + dp[i+ 2][j], dp[i][j]);
}
for (int K = i + 2; K <= j; K++){
if (str[i] == str[K]) {
dp[i][j] =
min(dp[i+1][K-1] + dp[K+1][j], dp[i][j]);
}
}
}
}
}
return dp[0][n - 1];
}
int main() {
string str = "3441213";
cout << "Minimum required steps: " <<
getMinRequiredSteps(str) << endl;
return 0;
}
위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.
실행 결과
Minimum required steps: 2
복잡도 분석
구간의 길이별로 모든 시작 위치를 순회하고, 내부에서 추가로 K 위치를 탐색하므로 시간 복잡도는 O(n³), 2차원 DP 테이블을 사용하므로 공간 복잡도는 O(n²)입니다. 문자열 길이가 수천 수준까지는 충분히 실용적인 성능을 보입니다.