Computer >> 컴퓨터 >  >> 프로그래밍 >> C++

C++로 문자열을 회문으로 만들기 위한 최소 삭제 횟수 구하기

문제 정의

길이가 n인 문자열이 주어졌을 때, 최소한의 문자를 삭제하여 해당 문자열을 회문(palindrome)으로 만드는 것이 목표입니다.

예를 들어 주어진 문자열이 "abcda"라면, 첫 번째 문자와 마지막 문자를 제외한 나머지 중 2개의 문자를 삭제하면 회문을 만들 수 있습니다.

  • 'b'와 'c'를 삭제하면 "ada"가 되어 회문입니다.
  • 'c'와 'd'를 삭제하면 "aba"가 되어 회문입니다.
  • 'b'와 'd'를 삭제하면 "aca"가 되어 회문입니다.

세 경우 모두 삭제 횟수는 2회로, 이것이 이 문자열에서 가능한 최소 삭제 횟수입니다.

접근 방식 및 알고리즘

이 문제의 핵심 아이디어는 최장 회문 부분 수열(Longest Palindromic Subsequence, LPS)과의 관계에 있습니다. 이미 회문인 가장 긴 부분 수열은 그대로 두고, 여기에 속하지 않는 문자만 제거하면 되기 때문입니다.

  1. 주어진 문자열에서 가장 긴 회문 부분 수열의 길이를 구합니다. 이를 lpsSize라고 합니다.
  2. 삭제해야 할 최소 문자 수 = 문자열 전체 길이 − lpsSize

예를 들어 "abcda"의 최장 회문 부분 수열은 "ada", "aba", "aca" 중 하나로 길이가 3이므로, 최소 삭제 횟수는 5 − 3 = 2가 됩니다.

C++ 구현 예제

#include <iostream>
#include <algorithm>
using namespace std;

// 인덱스 i부터 j까지 구간에서 최장 회문 부분 수열의 길이를 구하는 재귀 함수
int lps(string s, int i, int j){
    if (i == j) {
        return 1;
    }
    if (s[i] == s[j] && i + 1 == j) {
        return 2;
    }
    if (s[i] == s[j]) {
        return lps(s, i + 1, j - 1) + 2;
    }
    return max(lps(s, i, j - 1), lps(s, i + 1, j));
}

int minDeletion(string s){
    int n = s.size();
    int lpsSize = lps(s, 0, n - 1);
    return (n - lpsSize);
}

int main(){
    cout << "Minimum characters to be deleted = " <<
    minDeletion("abcda") << endl;
    return 0;
}

실행 결과

위 프로그램을 컴파일하고 실행하면 다음과 같은 결과가 출력됩니다.

Minimum characters to be deleted = 2

동작 원리 설명

  • 구간의 양 끝 문자가 같다면(s[i] == s[j]), 이 두 문자는 회문 부분 수열에 함께 포함될 수 있으므로 내부 구간(i+1 ~ j-1)의 결과에 2를 더합니다.
  • 양 끝 문자가 다르다면, 왼쪽 문자를 버리는 경우와 오른쪽 문자를 버리는 경우 중 더 큰 값을 선택합니다.
  • 마지막으로 전체 문자열 길이에서 LPS 길이를 빼면 제거해야 할 최소 문자 수가 됩니다.

시간 복잡도 및 개선 방안

위 재귀 구현은 동일한 하위 문제를 반복해서 계산하므로 시간 복잡도가 O(2ⁿ)까지 증가할 수 있습니다. 메모이제이션(memoization)을 적용하거나 2차원 DP 테이블(dp[i][j] = 구간 i~j의 LPS 길이)을 사용하면 시간 복잡도를 O(n²), 공간 복잡도 O(n²)로 개선할 수 있어 입력 크기가 큰 경우에도 효율적으로 동작합니다.