문자열 s가 주어졌을 때, 최대 k개의 문자를 삭제하여 이 문자열을 회문(palindrome)으로 만들 수 있는지 확인하는 문제입니다.
예를 들어 s = "lieuvrel", k = 4라고 가정해 보겠습니다. 이 경우 세 개의 문자를 삭제하면 회문인 "level"을 얻을 수 있으므로 결과는 True가 됩니다.
해결 접근 방법
이 문제는 최장 공통 부분 수열(LCS, Longest Common Subsequence) 알고리즘을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 문자열 s와 그 역순 문자열의 LCS 길이를 구합니다.
- LCS 길이는 곧 해당 문자열의 가장 긴 회문 부분 수열(LPS)의 길이와 같습니다.
- 따라서 전체 길이에서 LCS 길이를 뺀 값이 삭제해야 하는 최소 문자 수가 됩니다.
- 이 값이 k 이하이면 True, 초과하면 False를 반환합니다.
알고리즘 단계
- 두 문자열 a, b를 인자로 받는 함수 lcs()를 정의합니다.
- m := a의 길이, n := b의 길이로 설정합니다.
- (m + 1) x (n + 1) 크기의 테이블을 생성하고 0으로 초기화합니다.
- i를 1부터 m까지 반복하면서:
- j를 1부터 n까지 반복하며:
- a[i - 1]과 b[j - 1]이 같으면 table[i][j] := 1 + table[i - 1][j - 1]
- 그렇지 않으면 table[i][j] := max(table[i][j - 1], table[i - 1][j])
- j를 1부터 n까지 반복하며:
- table[m][n] 값을 반환합니다.
메인 로직에서는 len(s) - lcs(s, s의 역순) <= k 조건을 검사하여 참이면 True, 거짓이면 False를 반환합니다.
구현 예제
class Solution:
def solve(self, s, k):
def lcs(a, b):
m, n = len(a), len(b)
table = [[0] * (n + 1) for _ in range(m + 1)]
for i in range(1, m + 1):
for j in range(1, n + 1):
if a[i - 1] == b[j - 1]:
table[i][j] = 1 + table[i - 1][j - 1]
else:
table[i][j] = max(table[i][j - 1], table[i - 1][j])
return table[m][n]
return len(s) - lcs(s, s[::-1]) <= k
ob = Solution()
s = "lieuvrel"
k = 4
print(ob.solve(s, k))
입력
"lieuvrel", 4
출력
True
복잡도 분석
이 알고리즘의 시간 복잡도는 O(n²)이며, 공간 복잡도 역시 DP 테이블 저장을 위해 O(n²)입니다. 여기서 n은 문자열의 길이입니다. 문자열이 비교적 짧은 경우 매우 효율적으로 동작합니다.