[Gold 5] 17609 회문

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

17609번: 회문

 

이 문제는 투 포인터를 사용해서 회문인지 유사 회문인지 검사하면 해결할 수 있다.

 

문제에서 주어지는 회문 검사는 algorithm에 있는 reverse 함수를 통해서도 검사할 수 있다.

reverse 함수에 의해 구할 수 있는 결과는 유사 회문은 검사할 수 없다. 

따라서 회문인지 유사회문인지 그냥 문자열인지 한번에 판단하기 위해서 모든 검사를 투 포인터를 사용하는 것이 좋다.

 

회문인지는 0번째 인덱스(left)와 input.size() - 1번째 인덱스(right)에서 하나씩 검사하면 회문인지 판단 가능하다.

유사 회문인지는 left인덱스를 한칸 옮겨 검사한 결과와 right 인덱스를 한칸 옮겨 검사한 결과가 회문이면 유사 회문으로 판단할 수 있다.

유사 회문 검사를 시도 하였는데도 같은 문자가 발견되지 않는다면 그냥 문자열이 된다.

 

#include<iostream>
#include<string>
#include<algorithm>
using namespace std;

int N;
string input;
int isPalindrome(int left, int right, bool reTest) {
	while (left < right) {
		if (input[left] != input[right]) {
			if (reTest) {
				if (isPalindrome(left + 1, right, false) == 0 || isPalindrome(left, right - 1, false) == 0)return 1;
			}
			return 2;
		}
		left++;
		right--;
	}
	return 0;
}

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

	cin >> N;
	for (int i = 0; i < N; i++) {
		cin >> input;
		cout << isPalindrome(0, input.size() - 1, true)<<'\n';
	}
	return 0;
}