C++ 프로그램: 문자 'a'를 하나 추가해 회문이 아닌 문자열 만들기

문제 개요

소문자 영어 알파벳으로만 구성된 문자열 S가 있다고 가정해 보겠습니다. 우리는 이 문자열에 정확히 한 개의 문자 'a'를 삽입해야 합니다. 삽입한 결과가 회문(palindrome)이 아니게 만들 수 있다면 해당 문자열을 반환하고, 어떻게 삽입하더라도 회문이 된다면 "impossible"을 반환해야 합니다.

예를 들어 입력이 S = "bpapb"라면, 뒤에 'a'를 붙인 "bpapba"는 회문이 아니므로 이것이 정답이 됩니다.

해결 접근 방식

이 문제는 간단한 시행을 통해 해결할 수 있습니다. 먼저 문자열의 맨 뒤에 'a'를 붙였을 때 회문이 아닌지 확인하고, 그렇지 않다면 맨 앞에 'a'를 붙여 다시 확인합니다. 두 경우 모두 회문이라면 불가능하다고 판단합니다.

만약 S와 "a"를 연결한 문자열이 회문이 아니라면:
    S 뒤에 'a'를 붙인 문자열을 반환
그렇지 않고 "a"와 S를 연결한 문자열이 회문이 아니라면:
    'a' 뒤에 S를 붙인 문자열을 반환
두 경우 모두 해당하지 않으면:
    "Impossible"을 반환

회문 검사 함수의 동작

회문 검사 함수 p는 양쪽 끝에서부터 중앙으로 이동하며 각 위치의 문자가 일치하는지 비교합니다. 모든 문자 쌍이 일치하면 true(회문), 하나라도 다르면 false(비회문)를 반환합니다.

C++ 구현 예제

#include <bits/stdc++.h>
using namespace std;

bool p(const string& s) {
    for (int i = 0; i < s.size() / 2; i++)
        if (s[i] != s[s.size() - 1 - i])
            return false;
    return true;
}
string solve(string S) {
    if (!p(S + 'a'))
        return S + 'a';
    else if (!p('a' + S))
        return 'a' + S;
    else
        return "Impossible";
}
int main() {
    string S = "bpapb";
    cout << solve(S) << endl;
}

실행 결과

입력

"bpapb"

출력

bpapba

동작 원리 분석

입력 문자열 "bpapb"에 대해 프로그램은 다음과 같이 동작합니다.

• S + 'a' = "bpapba": 역순으로 읽으면 "abpapb"로 원래 문자열과 다르므로 회문이 아닙니다.
• 조건을 만족하므로 첫 번째 검사에서 즉시 "bpapba"를 반환합니다.

반면 S = "aaaa"처럼 모든 문자가 'a'로 이루어진 문자열은 어느 위치에 'a'를 추가하더라도 여전히 회문이 되기 때문에, 이 경우에는 "Impossible"이 반환됩니다.

복잡도 분석

회문 검사는 문자열 길이의 절반(N/2)만큼만 비교하므로 O(N)의 시간이 소요되며, 이 검사를 최대 두 번 수행하므로 전체 시간 복잡도는 O(N)입니다. 새 문자열을 생성하는 과정에서 공간 복잡도 역시 O(N)입니다.