C++로 문자열 S를 부분 수열로 갖는 회문 문자열 찾기

길이가 n인 문자열 S가 주어졌을 때, S를 부분 수열(subsequence)로 포함하면서 그 자체로 회문(palindrome)이 되는 또 다른 문자열 T를 찾는 문제입니다.

예를 들어 S = "ab"가 입력으로 주어지면 출력은 "aabaa"가 됩니다. 물론 정답은 하나로 정해져 있지 않으며, 조건을 만족하는 다른 문자열도 충분히 가능합니다.

해결 아이디어

접근 방법은 매우 직관적입니다. 원래 문자열 S에 S를 거꾸로 뒤집은 문자열을 그대로 이어 붙이면 됩니다. 이렇게 하면 결과 문자열이 좌우 대칭 구조를 갖게 되어 자동으로 회문이 되고, 앞부분에 원본 S가 온전히 남아 있으므로 부분 수열 조건 역시 자연스럽게 충족됩니다.

알고리즘 단계

이 문제는 다음 단계를 따라 해결할 수 있습니다.

res := S
S를 뒤집는다
res := res + S
res를 반환한다

C++ 구현 예제

아래 코드를 통해 실제 구현 과정을 더 자세히 살펴보겠습니다.

#include <bits/stdc++.h>
using namespace std;
string solve(string S){
    string res = S;
    reverse(S.begin(), S.end());
    res += S;
    return res;
}
int main(){
    string S = "ab";
    cout << solve(S) << endl;
}

입력

ab

출력

abba

동작 원리 상세 설명

S = "ab"가 주어진 경우를 단계별로 살펴보겠습니다. 먼저 res에 S를 그대로 복사하여 "ab"를 만든 뒤, S를 뒤집으면 "ba"가 됩니다. 이를 res에 이어 붙이면 최종 결과는 "abba"입니다. "abba"는 앞에서부터 읽어도 뒤에서부터 읽어도 동일한 회문이며, 앞의 두 글자가 정확히 "ab"이므로 S를 부분 수열로 포함하고 있습니다.

복잡도 분석

문자열을 한 번 순회하며 뒤집고 이어 붙이므로 시간 복잡도는 O(n)입니다. 공간 복잡도 역시 결과 문자열을 저장해야 하므로 O(n)입니다. 여기서 n은 문자열 S의 길이입니다.