15927번 : 회문은 회문아니야!!

https://www.acmicpc.net/problem/15927

15927번: 회문은 회문아니야!!

 

 

이 문제는, 과거에 풀다가 실패한 문제이다ㅠㅠ... 

 

 

---

 

 

어느정도 알고리즘을 풀어봤다면, 회문의 정의는 알 것이다. 이 문제는 주어진 문자열에서 회문이 아닌 부분 문자열의 최대 길이를 구하는 것이다.

 

 

 

 

뭔가 최대 길이를 구하라고 하니까, DP를 사용하고 싶었다. DP를 사용해서 풀면, 쉽긴 하지만 무조건 시간초과가 발생한다.

 

 

 

 

DP를 하면 최대 N * N이다. N의 최댓값은 500,000이므로 시간 초과는 당연하다.

 

 

 

 

그렇다면, 시간초과가 발생하지 않도록 해야 하는데, 주어진 문자열의 종류를 구분해보자.

 

 

 

 

1) 펠린드롬

2) 펠린드롬이 아닌 경우

 

 

 

 

이 두 가지의 경우에 정답은,

1) 문자열의 길이 - 1

2) 문자열의 길이

 

 

 

 

 

간단하게 두 가지라고 생각하고, 코드를 작성하다보면 "ZZZ"에서 올바르지 않은 값을 출력할 것이다. 이 경우에는, 문자열에서 하나의 문자를 제외해도 펠린드롬이 성립하기 때문이다. 

 

 

 

 

 

따라서, 펠린드롬인 경우, 위와 같은 특수한 케이스가 문제가 된다.

 

 

 

 

이 특수한 케이스가 어떤 규칙이 있는지를 파악해야 한다.

 

 

 

 

펠린드롬을 형성할 때, 문자열을 이루고 있는 문자가 모두 같다면 앞 혹은 뒤에서 연속적인 몇 개의 문자를 제외시켜도 항상 펠린드롬을 형성한다.

 

 

 

 

그렇다면, 문자열에서 하나 이상의 다른 문자가 있는데 펠린드롬을 이루고 있는 경우를 보자. 하나를 빼면 펠린드롬이 안되는 것을 증명해야 한다.

 

 

 

 

"ZZZZAZZZZ"

 

 

 

 

위의 경우를 생각해보면, A가 계속 중심에 있지 않은 이상 펠린드롬이 형성될 수 없다. 따라서, 문자열에서 하나 이상의 다른 문자가 있는 펠린드롬의 경우, 앞 혹은 뒤에서 1개의 문자만을 제외시켜도 펠린드롬이 형성되지 않는다.

 

 

 

 

즉, 모든 같은 문자로 이루어지지 않는 팰린드롬 문자열의 경우 정답은, "문자열의 길이 - 1" 이 된다.

 

 

 

 

---

 

 

 

 

해설코드(C++).

 

 

 

#include <iostream>
#include <string>
#include <algorithm>
#include <cstring>
 
using namespace std;
string str;
 
int main(void) {
    cin >> str;
    //str = "ZZZ";
    char same_check = str[0];
    bool same = true;
 
    for (int i = 0; i < str.size(); i++) {
        if (str[i] != str[str.size() - 1 - i]) {
            cout << str.size() << endl;
            return 0;
        }
        else {
            if (same_check != str[i])
                same = false;
        }
        // Stop
        if (i >= str.size() - i)
            break;
    }
 
    if (same)
        cout << -1 << endl;
    else
        cout << str.size() - 1 << endl;
    return 0;
}