C++로 문자열을 회문으로 만들기 위해 필요한 최소 문자 추가 개수 구하기

문제 정의

주어진 문자열의 뒤쪽에 문자를 추가하여 회문(palindrome)을 만들 때, 필요한 최소 추가 문자 개수를 구하는 문제입니다.

예시

문자열이 abcac라고 가정해 보겠습니다. 뒤에 2개의 문자를 추가하여 abcacba로 만들면 회문이 됩니다. 따라서 정답은 2입니다.

알고리즘

• 먼저 문자열이 이미 회문인지 확인합니다. 회문이라면 추가할 문자가 없으므로 0을 반환합니다.
• 회문이 아니라면, 앞에서부터 한 글자씩 제거하면서 남은 문자열이 회문인지 검사합니다.
• 남은 문자열이 회문이 될 때까지 이 과정을 재귀적으로 반복합니다.
• 앞에서 제거한 문자 수가 곧 뒤에 추가해야 할 문자 수와 같으므로, 제거된 문자 개수를 최종 답으로 반환합니다.

구현 예제 코드

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

bool isPalindrome(char *str) {
    int n = strlen(str);
    if (n == 1) {
        return true;
    }
    int start = 0, end = n - 1;
    while (start < end) {
        if (str[start] != str[end]) {
            return false;
        }
        ++start;
        --end;
    }
    return true;
}

int requiredAppends(char *str) {
    if (isPalindrome(str)) {
        return 0;
    }
    return 1 + requiredAppends(str + 1);
}

int main() {
    char *str = "abcac";
    cout << "Characters to be appended = " << requiredAppends(str) << endl;
    return 0;
}

코드 설명

isPalindrome 함수는 두 포인터(start, end)를 양 끝에서부터 안쪽으로 이동시키며 문자를 비교하는 방식으로 회문 여부를 판별합니다. requiredAppends 함수는 현재 문자열이 회문이 아니면 첫 글자를 건너뛰고(str + 1) 재귀 호출하며, 회문이 될 때까지 건너뛴 횟수를 누적해 반환합니다.

실행 결과

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

Characters to be appended = 2

복잡도 분석

이 접근 방식은 최악의 경우 각 단계마다 회문 검사에 O(n) 시간이 걸리고, 최대 n번 반복할 수 있으므로 전체 시간 복잡도는 O(n²)입니다. 더 큰 입력에 대해서는 KMP 알고리즘의 실패 함수(failure function)를 활용하면 O(n) 시간에 해결할 수 있습니다.