[ 백준 15927 ] 회문은 회문아니야!! (c/c++)

 

 

[ 문제요약 ]

길이가 50이하인 문자열이 주어질 때, 팰린드롬이 아닌 가장 긴 부분문자열의 길이를 출력한다. 그런 문자열이 없으면 -1을 출력한다.

 

 

[ 문제 풀이 ]

1. 만약 어떤 문자열이 팰린드롬이 아닌 경우 패린드롬이 아닌 가장 긴 부분문자열의 길이는 그 문자열의 전체 길이가 된다.

2. 만약 어떤 문자열이 팰린드롬일 경우 가장 마지막 문자를 제외한 문자열이 가장 긴 부분문자열이 된다.

3. 만약 어떤 문자열의 모든 문자가 같은 경우 그런 부분문자열이 없다.

4. 팰린드롬인지 판단하기 위해서는 문자열의 처음과 마지막 문자를 비교하고 2번째 문자를 비교하고 마지막 이전의 문자를 비교하다가 문자열의 길이의 절반까지 탐색했을 때 모든 문자가 같았으면 팰린드롬이다.

 

 

[ 소스 코드 ]

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

string str;
int ans = 1;
map<char, int> m;

int main() {
    cin >> str;

    for (int i=0; i<str.size()/2; i++){
        if (str[i] != str[str.size()-i-1]){
            ans = 0;
            break;
        }
    }

    for (int i=0; i<str.size(); i++) m[str[i]] = m[str[i]] + 1;
    if (m[str[0]] == str.size()) ans = 2;

    if (ans == 1) cout << str.size() - 1;
    else if (ans == 2) cout << "-1";
    else cout << str.size();
    
    return 0;
}

 

 

[ 주의할 점 ]

만약 문자열에 문자가 하나만 주어지는 경우 부분문자열을 만들 수 없다.