[BOJ 15927] 회문은 회문아니야!!

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

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

 

- 문제 요약

 

알파벳 대문자로 이루어진 문자열이 주어졌을 때, 팰린드롬이 아닌 가장 긴 부분 문자열의 길이를 구해 보자. 이때 부분 문자열을 이루는 글자는 연속해야 한다. 팰린드롬이 아닌 부분 문자열이 없다면 -1을 출력한다.

 

 

- 알고리즘 정리

 

우선 가장 긴 팰린드롬을 만들기 위해서는 문자열의 양 끝 문자가 달라야 합니다.

 

Tast case 2를 예로 들면 "PALINDROME" 이라는 문자열은 가장 양 끝 문자인 P와 E가 다르기 때문에 가장 긴 팰린드롬의 길이는 문자열의 전체 길이인 10이 될 것입니다.

 

또한, Tast case 3을 보면 모든 문자가 다 같을 경우에는 팰린드롬이 아닌 부분문자열이 없기 때문에 -1이 출력됩니다.

 

그리고 어떤 문자열이 회문일 때 가장 앞 글자나 가장 끝 글자를 제외하면 회문이 아니게 됩니다.

그러므로 Tast case 1의 경우인 "ABCBA"에서 가장 앞 글자인 A를 빼면 BCBA가 되므로 답은 4가 됩니다.

 

이제 코드를 짜기 위해 이 내용들을 순서대로 정리해보겠습니다.

 

1. 이 문자열이 회문인지 아닌지 판별한다.
2. 회문이 아니라면 문자열 전체의 길이를 출력한다.
3. 회문이라면 문자열 내의 모든 문자가 같은지 판별한다.
4. 모든 문자가 같지 않다면 전체 문자열 길이에서 1을 뺀 값을 출력한다.
5. 모든 문자가 같다면 -1을 출력한다.

 

이제 이 알고리즘을 바탕으로 코드를 짜보겠습니다.

 

 

- 코드 작성

 

우선 이 문자열의 특성을 판별해야 하니 변수가 필요할 것 같습니다.

회문인지 아닌지를 판별하는 변수, 모든 문자가 같은지 아닌지를 판별하는 변수, 이렇게 두 변수가 필요할 것 같습니다.

 

#include<cstdio>
#include<iostream>
using namespace std;

string a;
int co1,co2;

int main(){
	cin>>a;
	for(int i=0;i<a.size()/2;i++){
		if(a[i]!=a[a.size()-i-1]){
			co1=1;
			break;
		}
		else if(a[i]!=a[i+1]){
			co2=1;
		}
	}
	if(co1==1){
		cout<<a.size();
	}
	else{
		if(co2==1){
			cout<<a.size()-1;
		}
		else{
			cout<<-1;
		}
	}
}

코드 제출 결과

회문이 어떻게 만들어지는지를 곰곰이 생각해보면 쉽게 풀리는 문제였습니다.

코드 구현 자체는 쉽지만 아이디어를 만들어 내는 것이 꽤 힘들었습니다.