C++에서 문자열 A를 부분 수열로 포함하는 회문 문자열 B 만들기

문자열 A가 주어졌을 때, 회문(palindrome)에 해당하는 또 다른 문자열 B를 찾아야 하며, 이때 주어진 문자열 A는 반드시 B의 부분 수열(subsequence)이어야 합니다.

여기서 부분 수열이란, 원본 문자열에서 일부 문자를 삭제하더라도 남은 문자들의 순서는 그대로 유지한 상태로 만들 수 있는 문자열을 의미합니다. 예를 들어 문자열이 "cotst"라면, 여기서 파생될 수 있는 문자열 중 하나가 "contest"입니다. 이 프로그램에서는 입력으로 A = "ab"를 사용하며, 그 결과 생성되는 문자열은 "abba"로 회문이 됩니다.

해결 접근 방식

이 문제를 해결하는 방법은 매우 간단합니다. 먼저 문자열 A를 뒤집은 후, 뒤집힌 문자열을 원래 A 뒤에 이어 붙여 B를 만드는 것입니다. 즉, 다음과 같이 표현할 수 있습니다.

B = A + reverse(A)

이렇게 하면 문자열의 앞부분과 뒷부분이 서로 대칭을 이루므로 결과 문자열은 항상 회문이 되고, 원래 문자열 A가 그대로 포함되어 있으므로 부분 수열 조건 역시 자연스럽게 만족하게 됩니다.

예제

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

bool isPalindrome(string str) {
    string temp = str;
    reverse(str.begin(), str.end());
    return str == temp;
}

string formPalindromeStr(string A) {
    string B = A;
    reverse(A.begin(), A.end());
    A = A + B;
    if (isPalindrome(B))
        return B;
    return A;
}

string reverse(string input) {
    string temp = input;
    int left, right = 0;
    right = temp.length() - 1;
    for (left = 0; left < right; left++, right--)
        swap(temp[left], temp[right]);
    return temp;
}

int main(int argc, char const *argv[]) {
    string A = "Hello";
    cout << "The B is: " << formPalindromeStr(A);
}

출력

The B is: olleHHello

코드 설명

isPalindrome(): 문자열의 복사본을 만든 뒤 원본을 뒤집어 서로 비교함으로써, 해당 문자열이 회문인지 여부를 판별합니다.

formPalindromeStr(): 입력 문자열 A를 복사하여 B에 저장하고, A를 뒤집은 뒤 원본을 뒤에 이어 붙여 새로운 문자열을 구성합니다. 만약 A 자체가 이미 회문이라면 그대로 반환하고, 그렇지 않다면 A + reverse(A) 형태의 회문 문자열을 반환합니다.

reverse(): 왼쪽과 오른쪽 인덱스를 가리키는 두 포인터를 활용해 문자열을 제자리에서 뒤집는 보조 함수입니다.

입력이 "Hello"인 경우, 뒤집은 문자열 "olleH" 뒤에 원본 "Hello"를 이어 붙여 최종적으로 "olleHHello"라는 회문 문자열이 생성됩니다.