C++에서 주어진 문자열이 회전 회문인지 확인하는 방법

이 글에서는 주어진 문자열을 몇 번 회전했을 때 회문(palindrome)이 되는지 확인하는 방법을 살펴봅니다. 회문이란 앞에서 읽으나 뒤에서 읽으나 동일한 문자열을 의미합니다.

예를 들어 "AAAAD"라는 문자열은 그 자체로는 회문이 아닙니다. 하지만 이를 한 칸 회전하면 "AADAA"가 되는데, 이는 회문입니다. 이처럼 적절히 회전하면 회문이 되는 문자열을 '회전 회문(rotated palindrome)'이라고 합니다.

접근 방법

문자열이 회전 회문인지 확인하는 기본적인 절차는 다음과 같습니다.

1. 먼저 원본 문자열이 회문인지 검사합니다.
2. 회문이 아니라면 문자열을 한 문자씩 회전시킨 뒤 다시 회문 여부를 검사합니다.
3. 이 과정을 문자열 길이 n번만큼 반복하며, 단 한 번이라도 회문이 발견되면 해당 문자열은 회전 회문으로 판단합니다.

이 방법은 가능한 모든 회전 상태를 빠짐없이 검사하므로 정확하지만, 시간 복잡도는 O(n²)입니다.

C++ 구현 예제

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

// 지정된 구간 [left, right]가 회문인지 재귀적으로 검사하는 함수
bool isPalindromeRange(string str, int left, int right){
    return (left >= right) || (str[left] == str[right] && isPalindromeRange(str, left + 1, right - 1));
}

// 문자열의 모든 회전 상태에 대해 회문 여부를 검사하는 함수
bool isRotatedPalindrome(string str){
    int len = str.length();
    for (int i = 0; i < len; i++){
        rotate(str.begin(), str.begin() + 1, str.end()); // 문자열을 한 칸 왼쪽으로 회전
        if (isPalindromeRange(str, 0, len - 1)) // 회전된 문자열이 회문이면 true 반환
            return true;
    }
    return false;
}

int main(){
    string str = "AAAAD"; // 회전하면 AADAA가 되어 회문이 됨
    if (isRotatedPalindrome(str))
        cout << "Its rotation is palindrome";
    else
        cout << "Its rotation is not palindrome";
}

코드 설명

isPalindromeRange() 함수는 두 개의 인덱스(left, right)를 받아 해당 구간이 회문인지 재귀적으로 확인합니다. 양 끝의 문자가 서로 같으면 안쪽 구간을 다시 검사하는 방식으로 동작하며, 포인터가 교차하거나 만나면 true를 반환합니다.

isRotatedPalindrome() 함수는 STL의 rotate() 알고리즘을 사용해 문자열을 한 칸씩 왼쪽으로 회전시키며, 매 회전마다 전체 문자열에 대해 회문 검사를 수행합니다. n번의 회전을 모두 시도했음에도 회문이 발견되지 않으면 false를 반환합니다.

실행 결과

Its rotation is palindrome

"AAAAD"는 자체적으로는 회문이 아니지만, 회전된 상태인 "AADAA"에서 회문이 되므로 위와 같은 결과가 출력됩니다.