문제 소개
하나의 문자열 s가 주어졌을 때, 이를 여러 개의 부분 문자열로 나누되 모든 조각이 회문(palindrome)이 되도록 하려면 몇 번 잘라야 할까요? 이 문제에서는 필요한 최소 자르기(cut) 횟수를 구하는 것이 목표입니다.
예를 들어, 문자열이 "ababba"라면 다음과 같이 두 번 잘라 세 개의 조각으로 나눌 수 있습니다.
[aba | bb | a]
"aba"도 회문이고, "bb"도 회문이며, 마지막 한 글자 "a" 역시 회문입니다. 따라서 정답은 2가 됩니다.
풀이 전략: 동적 계획법(DP)
이 문제는 동적 계획법을 활용하면 체계적으로 해결할 수 있습니다. 알고리즘의 진행 과정은 다음과 같습니다.
- n := 문자열 s에 포함된 문자 개수
- 크기가 n + 1인 배열 res 생성
- res[n] := -1로 초기화 (경계 처리용)
- i를 n − 1부터 0까지 역순으로 반복:
- res[i] := n − i − 1로 초기화
- j를 i부터 n − 1까지 반복:
- 부분 문자열 s[i..j]가 회문이라면,
res[i] := min(res[i], 1 + res[j + 1])로 갱신
- 부분 문자열 s[i..j]가 회문이라면,
- 최종 답으로 res[0] 반환
핵심 아이디어는 다음과 같습니다. res[i]는 "i번째 인덱스부터 문자열 끝까지 남은 부분을 회문 조각으로 분할할 때 필요한 최소 컷 수"를 의미합니다. s[i..j]가 회문이라면, 이 구간을 하나의 조각으로 묶고 남은 뒷부분에 대한 최소 컷 수(res[j + 1])에 1을 더한 값이 후보가 됩니다.
여기서 res[n]을 −1로 초기화하는 이유도 중요합니다. 만약 s[i..n−1] 전체가 회문이라면 j = n − 1일 때 res[i] = 1 + res[n] = 0이 되어, 추가로 자를 필요 없이 통째로 하나의 회문임을 올바르게 반영할 수 있습니다. 또한 초기값 n − i − 1은 각 문자를 모두 개별 조각으로 쪼개는 최악의 경우를 대비한 값입니다.
C++ 구현 예제
아래 코드를 보면 더 쉽게 이해할 수 있습니다.
#include <bits/stdc++.h>
using namespace std;
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];
}
class Solution {
public:
int minCut(string s) {
return solve(s);
}
};
main(){
Solution ob;
cout << (ob.minCut("ababba"));
}
입력
"ababba"
출력
2
복잡도 분석 및 최적화 팁
위 구현은 시작 위치 i와 끝 위치 j의 조합이 O(n²)개이고, 매번 회문 검사에 최대 O(n)의 시간이 소요되므로 전체 시간 복잡도는 O(n³), 공간 복잡도는 O(n)입니다.
성능을 더 끌어올리고 싶다면, 사전에 2차원 DP 테이블 isPal[i][j]를 만들어 모든 구간의 회문 여부를 미리 계산해 두는 방법을 사용할 수 있습니다. 이렇게 하면 회문 검사를 O(1)로 처리할 수 있어 전체 시간 복잡도를 O(n²)까지 줄일 수 있습니다.