[1일 1백준] 15927 - 회문은 회문아니야!!

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

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

어떤 임의의 문자열에 대해서, 회문이 아닌 문자열 중 제일 긴 것의 길이를 반환하는 문제이다.

 

풀면서 여기에 내가 세운 몇가지 법칙들과 가설을 적어 놓고, 풀어보려고 한다. [n..m]은, n번째 인덱스 부터 m번째 인덱스 까지의 문자열을 말한다. 인덱스는 0에서 시작하고 n-1로 끝난다. 예를 들어, "ABCD" 라는 문자열에서 [0..2] = "ABC"이다.

 

1,2는 회문의 정의에 따른 성질, 3,4는 명제/증명.

$$ n < m $$

1. n번째 문자와 m번째 문자가 다르다면, [n..m]은 회문이 아니다. (이건 확실, 확장한게 4번)

2. [n..m]까지의 문자열에서, $k \le (m - n) / 2$인 임의의 음이 아닌 정수 k에 대해서 n + k번째, m - k번째 문자가 같지 않다면, [n..m]은 회문이 아니다.

 

3. [n..m]이 회문이고 [n-1..m]이 회문이 아니라면, [n..m-1]도 회문이 아니다.

4. [n..m]이 회문이고 [n..m-1]도 회문인 경우는 [n..m]이 하나의 문자로 이루어진 경우 뿐이다.

 

<증명>

어떤 [n..m]이 회문일때, 2에 의해서, $k \le (m - n) / 2$인 임의의 음이 아닌 정수 k에 대해서 n + k번째, m - k번째 문자는 각각 같다. 여기서 1글자를 추가해서 [n..m+1]의 글자도 회문이려면, 비슷하게 $k \le (m + 1 - n) / 2$인 임의의 음이 아닌 정수 k에 대해서 n + k번째, m + 1 - k번째 문자도 각각 같다.

 

아래의 그림을 보자.

따라서 4번의 명제는 참이라고 할 수 있다.

일단 생각나는 것들을 몇 개 넣어놓은 것이기 때문에, 정작 알고리즘을 짤 땐 필요 없을지도....

 

내가 생각하는 알고리즘은 이렇다.

1. 전체 문자열에 대해서 회문인지 아닌지를 판별한다.

1-1.동시에, 문자열이 'ZZZ...ZZZ' 같은 하나의 문자로만 이루어진 문자열인지 판별한다.

 

2.

만약, 회문이 아니라면,

-> 답은 n

회문이라면,

-> 만약 하나의 문자열로 이루어져 있다면, 답은 -1, 언제나 회문.

-> 만약 그렇지 않다면, 앞의 4번에 의해서, 답은 n - 1. (이미 [0..n]이 회문인데, [0..n-1]도 회문이라면 단순문자열 이어야 하나, 그렇지 않으므로 모순이 발생, 따라서 [0..n-1]은 무조건 회문이 아님.)

 

코드 :

#include<iostream>

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    bool is_simple = true, is_pel = true;
    int n;
    char first;
    string pel;
    cin >> pel;
    n = pel.length();
    first = pel[0];

    for(int i = 0; i < (n + 1) / 2; i++){
        if(pel[i] != pel[n - i - 1]){
            is_pel = false;
            break;
        }
        if(first != pel[i] || first != pel[n - i - 1])
            is_simple = false;
    }

    if(is_pel){
        if(is_simple)
            cout << "-1\n";
        else
            cout << n - 1 << '\n';
    } else {
        cout << n << '\n';
    }

    return 0;
}

 이렇게 풀이 적으면서 푸니까 그래도 뭔가 기분은 좋다. 나름의 성취감이 있는듯. 앞으로도 이렇게 포스팅 하면서 문제를 푸는게 좋을 것 같다.