E. No Palindromes (Codeforces Global Round 25)

• 링크

https://codeforces.com/contest/1951/problem/E

• 내가 푼 방법

일단 전체가 팰린드롬이 아니라면, 바로 YES를 반환하고 s를 출력한다. 그러고서 처음으로 다른 문자가 나오는 것을 기록해 준다. 만일 전부 다 같은 글자이면 절대로 서브스트링이 팰린드롬이 아닐 수가 없으므로 no 를 출력해 준다. 이제 진짜다. 처음으로 찾은 다른 글자까지는 무조건 팰린드롬이 아니다. 즉, 0~firstDiff까지의 서브스트링이 절대로 팰린드롬이 아니다. 그러면 여기서 firstDiff+1~n-1까지의 서브스트링이 팰린드롬이 아니기만 하면 문제는 끝이다.

하지만, 팰린드롬이라면? 여기서부터는 조금 복잡해진다. 여기서 firstDiff=2와 중간인 경우를 볼 수 있다. (총길이가 짝수이면 안 된다.) 그러면 firstDiff가 중간인 경우는 aba (a와 b는 패턴을 의미한 것) 이렇게 이루어질 것이다.
이유는? 또한 짝수일 수 없는 이유도 여기서 나온다. 여기서 주의할 점은 전체 문자열이 팰린드롬이고, 중간 이후부터도 팰린드롬이라는 것이다. 그러면 무조건 aaabaaa 이런 식으로 나올 수밖에 없다. 즉, b 다음에 무조건 똑같은 글자만이 나올 수밖에 없다는 것이다.

이유는 중간에서 처음 다른 글자를 발견하였고 전체가 팰린드롬이기에 b이전의 글자와 이후의 글자는 동일할 수밖에 없는 것이다. 만일 짝수라면? aaabbaaa 이런 식이 될 것이다. 이러면 baaa 가 팰린드롬이 아니기에 여기에 포함되지 않는 것이다. 그러면 이제 firstDiff 가 2인 경우를 봐보자. 글자가 6개인 경우 ab로 시작하면?

ab____인데, 여기서 주의할 점은 맨 마지막에서 두 글자는 ab를 뒤집은 것과 동일하다는 것이다. ab__ba 이렇게 되어야 한다. 근데 이제 ab 다음 __ba가 팰린드롬이여야 하니까 abba가 되어야 한다. 즉, ababba 인 것인데, 이러면 전체가 팰린드롬이 아니다. 분명히 따라야 하는 규칙에 따라 수를 구성해 나갔는데, 구성하고 나니 팰린드롬이 아니게 되었다. 이 말은 길이가 짝수면 절대로 firstDiff 이후가 팰린드롬이 아니어야 한다는 말이다. (전체가 팰린드롬이니까) 그럼 홀 수면 어떻게 될까?

ab___ba가 되고 또 팰린드롬을 만들기 위해 firstDiff 이후 두 글자를 채우면 abab_ba가 된다. 마지막 하나 남은 자리에는 당연히 a가 들어가야지, 전체가 팰린드롬이 되기 때문에 abababa가 되게 된다. firstDiff가 2이면서 firstDiff 이후가 팰린드롬이 아닌 경우, 무조건 a와 b가 번갈아 오는형태가 구성된다는 것이다.

a와 b가 반복되는 경우 하나라도 홀수개의 서브스트링을 구성하면 무조건 팰린드롬이 된다. 하지만, 길이가 홀 수이기 때문에, 최소 한 번은 홀 수개의 서브스트링을 구성해야 한다. 그러니 절대로 모두 팰린드롬이 아닌 서브스트링을 구성할 수 없는 경우이다. 이 이외의 경우는 모두 답을 도출해 낼 수 있다. 그 방법은 바로 firstDiff를 기점으로 두 영역으로 나누는 것이 아닌, firstDiff+1을 기점으로 두 영역을 나누는 것이다.

생각해보자. 모두 팰린드롬, 그리고 firstDiff+1이후로도 팰린드롬이었다.
이것도 구체적인 예시로 생각을 해보자. 1112로 시작하며 총길이는 11인 문자열을 생각해 보자. 그러면 동일하게 맨 뒤에 2111을 넣어줘야 한다. 1112___2111가 될 것이다. 그러면 가운데는 정해졌다. 바로 111이 들어가야 한다. 왜? firstDiff 이후의 서브스트링도 팰린드롬이었으니까. 그래서 전체적으로 11121112111이다.

11121 112111을 나누면 서브스트링이 모두 팰린드롬이 아니다. 이것은 당연하다. firstDiff가 2가 아니었기 때문에 firstDiff에 앞서 같은 글자가 2개 이상 있다. 그 의미는 무조건 firstDiff 바로 이후에도 같은 글자가 2개 이상 있다는 것이고, 그와 동일하게 맨 마지막에도 같은 글자가 2개 이상 있다. 이는 2개 이상이라고 포함했지만, 2개 이상이면서 같은 개수의 글자가 반복되고, 그렇기 때문에 한 글자만 뒤로 더 포함하더라도 균형이 깨지는 것이다.

예시로도 보면 1112 뒤에 1112111 이었는데, 어차피 여기서 11121 에서 볼 수 있듯 뒤에 하나 추가한다고 해서 절대로 팰린드롬이 될 수 없는 것을 볼 수 있고, 112111 처럼 맨 앞 1을 이전 서브스트링에 양보해 균형이 깨진 것을 볼 수 있다.

이렇게 해서 답을 구할 수 있는 문제였다. 아주 재미있는 문제였다.

• 시간 복잡도

O(N)

• Correct Code

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

string s;

bool isPal(int l, int r) {
    while (l < r) {
        if (s[l++] != s[r--]) {
            return false;
        }
    }
    return true;
}

void solve() {
    cin >> s;
    int n = s.size();
    if (!isPal(0, n - 1)) {
        cout << "YES\n1\n" << s << "\n";
        return;
    }
    int firstDiff = -1;
    for (int i = 1; i < n; ++i) {
        if (s[i] != s[0]) {
            firstDiff = i;
            break;
        }
    }
    if (firstDiff == -1) {
        cout << "NO\n";
        return;
    }
    if (!isPal(firstDiff + 1, n - 1)) {
        cout << "YES\n2" << "\n";
        cout << s.substr(0, firstDiff + 1) << " " << s.substr(firstDiff + 1) << "\n";
    } else if (n % 2 == 1 && (firstDiff == 1 || firstDiff == n / 2)) {
        cout << "NO\n";
    } else {
        cout << "YES\n2" << "\n";
        cout << s.substr(0, firstDiff + 2) << " " << s.substr(firstDiff + 2) << "\n";
    }
}

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    freopen("e.input.txt", "r", stdin);
    int T;
    cin >> T;
    while (T-- > 0) {
        solve();
    }
    return 0;
}