[BOJ / C++] 15927번 : 회문은 회문 아니야!!

문제

팰린드롬이란 앞으로 읽으나 뒤로 읽으나 같은 문자열을 말한다. 팰린드롬의 예시로 POP, ABBA 등이 있고, 팰린드롬이 아닌 것의 예시로 ABCA, PALINDROME 등이 있다.

같은 의미를 가지는 여러 단어들을 보자.

• 회문 (한국어)
• palindrome (영어, 프랑스어, 노르웨이어, 그리스어, 라틴어)
• 回文 (일본어, 중국어)
• palindrom (독일어, 덴마크어)
• palindromi (핀란드어)
• palíndromo (스페인어, 포르투갈어)
• palindromo (이탈리아어, 에스페란토어)
• палиндром (러시아어)
• قلب مستو (아랍어)

뭔가 이상한 점이 보이지 않는가? 그 어떤 언어에서도 팰린드롬을 뜻하는 단어는 팰린드롬이 아니다! 많은 사람들이 추구하는 “대칭의 아름다움”은 그저 허상에 불과하다.

알파벳 대문자로 이루어진 문자열이 주어졌을 때, 팰린드롬이 아닌 가장 긴 부분문자열의 길이를 구해 보자. 이때 부분문자열을 이루는 글자는 연속해야 한다. AB는 ABCD의 부분문자열이지만, AC는 아니다.

입력

길이가 1 이상 50만 이하인 문자열이 주어진다.

출력

팰린드롬이 아닌 가장 긴 부분문자열의 길이를 출력한다. 그런 부분문자열이 없으면 -1을 출력한다.

Solved.ac 레벨

골드 V

풀이

오늘은 먼저 제출했다가 틀린 코드를 보자.

#include <bits/stdc++.h>

using namespace std;

vector<int> v;

//팰린드롬 체크
bool chkPal(string s) {
    int strLen = s.length();
    for(int i = 0; i < strLen; i++) {
        if(s[i] != s[strLen - i - 1]) {
            return false;
        }
    }
    return true;
}

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

    string str;
    cin >> str;
    int strLen = str.length();
    string tmp = "";

    for(int i = 0; i < strLen; i++) {
        tmp = "";
        for(int j = i; j < strLen; j++) {
            tmp += str[j];
			//해당 길이까지의 문자열 제작
            if(!chkPal(tmp)) {
            //제작된 문자열이 팰린드롬이 아니면 해당 문자열의 길이를 벡터에 저장
                v.push_back(tmp.length());
            }
        }
    }

    if(v.size() == 0) {
        cout << -1 << "\n";
    } else {
   		//팰린드롬이 아닌 문자열들의 길이 중 최대값을 출력.
        cout << *max_element(v.begin(), v.end()) << "\n";
    }

    return 0;
}

답은 예제 입출력과 동일하게 나왔으나 채점시 시간초과가 떴다.

이 문제의 유형은 '애드 혹'으로 문제를 풀기 위해 정형화된 과정이 없음을 다시 상기해보면 답은 생각보다 쉬웠다.

#include <bits/stdc++.h>

using namespace std;

//팰린드롬인지 체크
bool chkPal(string s) {
    int strLen = s.length();
    for(int i = 0; i < strLen; i++) {
        if(s[i] != s[strLen - i - 1]) {
            return false;
        }
    }
    return true;
}

//문자열의 모든 문자가 동일한지 체크
bool chkSame(string s) {
    int strLen = s.length();

    int tmp = s[0];
    for(int i = 1; i < strLen; i++) {
        if(s[i] != tmp) {
            return false;
        }
    }
    return true;
}

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

    string str;
    cin >> str;
    int strLen = str.length();

    if(chkPal(str)) {
        if(chkSame(str)) {
        	//모두 같은 문자열은 무조건 팰린드롬, 팰린드롬이 아닌 부분 문자열이 없다.
            cout << -1 << "\n";
        } else {
        	//팰린드롬일 경우, 왼쪽 혹은 오른쪽의 문자 하나만 없애면
            //가장 긴 길이의 팰린드롬이 아닌 부분문자열이다.
            cout << strLen - 1 << "\n";
        }
    } else {
    	//팰린드롬이 아니라면 팰린드롬이 아닌 가장 긴 부분 문자열은 
        //입력받은 문자열 그 자체다.
        cout << strLen << "\n";
    }

    return 0;
}

 

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