백준15927 회문은 회문아니야!!

작성일 | In

문제 링크

  • http://icpc.me/15927

문제 출처

  • 제2회 천하제일 코딩대회 L번

시간복잡도

  • O(n)

풀이

먼저, 전체 문자열이 팰린드롬인지 검사를 해보고 (1번 조건), 팰린드롬이 아니라면 전체 문자열의 길이를 출력하고 프로그램을 종료합니다.
그 다음에는 맨 뒷 글자를 제외한 나머지 문자열이 팰린드롬인지 검사를 해보고 (2번 조건), 팰린드롬이 아니라면 해당 문자열의 길이를 출력하고 프로그램을 종료합니다.

1번 조건과 2번 조건을 모두 통과한 경우를 살펴봅시다.
1번 조건을 통과했으면 전체 문자열이 팰린드롬이므로 1 2 3 4 … 4 3 2 1 형태로 되어있을 겁니다.
맨 뒷 글자를 제거하면 1 2 3 4 … 4 3 2 형태로 되어있겠네요.
2번 조건을 통과했다면 1 2 3 4 … 4 3 2 도 팰린드롬이라는 것입니다.
그 말은, 1과 2가 같고 2와 3이 같고 … 결론적으로 모든 문자가 다 같기 때문에 -1을 출력해주면 됩니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
#include <bits/stdc++.h>
using namespace std;

bool isPal(string a, int l, int r){
	while(l<r){
		if(a[l] != a[r]) return 0;
		l++; r--;
	}
	return 1;
}

int main(){
	string a; cin >> a;
	if(!isPal(a, 0, a.size()-1)) cout << a.size();
	else if(!isPal(a, 0, a.size()-2)) cout << a.size()-1;
	else cout << -1;
}