문제 개요
문자열 s와 정수 k가 주어졌을 때, 해당 문자열이 K-회문(K-Palindrome)인지 판별하는 문제입니다.
여기서 K-회문이란, 문자열에서 최대 k개의 문자를 제거했을 때 회문(palindrome)으로 변환할 수 있는 문자열을 의미합니다.
예를 들어 입력이 s = "abcdeca", k = 2라고 가정해 보겠습니다. 이 경우 'b'와 'e' 두 문자를 제거하면 "acdca"가 되는데, 이는 앞에서 읽으나 뒤에서 읽으나 같은 회문입니다. 따라서 출력 결과는 true(1)가 됩니다.
접근 방법: 최장 공통 부분 수열(LCS) 활용
이 문제의 핵심 아이디어는 다음과 같습니다. 문자열을 회문으로 만들기 위해 제거해야 하는 최소 문자 수는 전체 문자열 길이에서 원본 문자열과 뒤집은 문자열 사이의 최장 공통 부분 수열(LCS, Longest Common Subsequence) 길이를 뺀 값과 같습니다.
즉, s.size() - lcs(s, reverse(s)) <= k 조건을 만족하면 해당 문자열은 K-회문입니다.
알고리즘 단계
- 두 문자열 s와 t를 받아 LCS 길이를 반환하는
lcs()함수를 정의합니다. - n := s의 길이로 설정하고, 인덱스 계산을 편리하게 하기 위해 s와 t 앞에 각각 공백 한 칸을 추가합니다.
- 크기가 (n+1) × (n+1)인 2차원 배열 dp를 선언합니다.
- i를 1부터 n까지 반복하며, 내부에서 j를 1부터 n까지 반복합니다.
- dp[i][j] := max(dp[i-1][j], dp[i][j-1])
- 만약 s[i]와 t[j]가 같다면, dp[i][j] := max(dp[i][j], 1 + dp[i-1][j-1])
- 최종적으로 dp[n][n] 값을 반환합니다.
메인 로직
- 문자열 s가 비어 있다면 true를 반환합니다.
- 문자열 s를 뒤집은 새로운 문자열 x를 생성합니다.
s.size() - lcs(s, x) <= k의 참/거짓 여부를 반환합니다.
아래 예시 코드를 통해 더 자세히 이해해 보겠습니다.
예제 코드
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int lcs(string s, string t){
int n = s.size();
s = " " + s;
t = " " + t;
vector<vector<int> > dp(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
if (s[i] == t[j])
dp[i][j] = max(dp[i][j], 1 + dp[i - 1][j - 1]);
}
}
return dp[n][n];
}
bool isValidPalindrome(string s, int k) {
if (!s.size())
return true;
string x = "";
for (int i = s.size() - 1; i >= 0; i--)
x += s[i];
return s.size() - lcs(s, x) <= k;
}
};
main(){
Solution ob;
cout << (ob.isValidPalindrome("abcdeca", 2));
}입력
"abcdeca", 2
출력
1
복잡도 분석
이 알고리즘의 시간 복잡도는 LCS 계산을 위해 O(n²)이며, 공간 복잡도 역시 2차원 DP 테이블 사용으로 O(n²)입니다. 문자열 길이가 수천 수준까지는 충분히 빠르게 동작하지만, 더 긴 문자열에는 구간별 DP나 메모이제이션 최적화를 고려할 수 있습니다.