[C++] 백준 17609번: 회문

문제 링크

17609번: 회문

문제 요약

주어진 문자열이 회문인지, 유사회문인지, 그 외인지 판별해야한다.
회문은 앞뒤로 봤을 때 순서가 같은 문자열이며, 유사회문은 문자열에서 문자 하나를 제거했을 때 회문이 되는 문자열을 말한다.

접근 방법

문자열의 양 끝단에서 시작해 두 포인터로 풀 수가 있습니다. 하지만 유사회문의 경우는 잘 처리해줄 필요가 있습니다. 유사회문인 경우에는 문자 하나를 건너뛴 다음에 검사를 이어나가야 합니다. 그런데 두 문자 중 어떤 문자를 건너 뛰어야할지 판단을 내려야할 필요가 있습니다.

ASDSAS

이러한 입력이 주어지고 양 끝에서 회문 검사를 시작한다고 가정해보겠습니다.

ASDSAS

제일 처음에 A와 S를 비교하게 되는데 이 둘은 다른 문자입니다. 따라서 이 문자열은 회문은 아니게 됩니다. 이제는 A와 S 중에 하나를 건너 뛰고 유사회문이 될 수 있는지를 검사해 줄 수 있습니다.

만약 앞의 A를 건너뛴다고 하면

ASDSAS

이 문자열은 유사회문도 될 수 없음을 알 수 있습니다.

ASDSAS

하지만 뒤의 S를 건너 뛴다면 이 문자열은 유사회문이 될 수 있음을 알 수 있습니다.

따라서 회문 검사를 하다가 두 문자가 다른 경우를 최초로 발견하게 된다면 앞의 문자, 뒤의 문자를 건너 뛴 경우를 각각 검사해볼 필요가 있습니다.

코드

#include <bits/stdc++.h>
#define VPRT(x, type) copy(x.begin(), x.end(), ostream_iterator<type>(cout, " "))
#define ALL(x) x.begin(), x.end()
#define FASTIO ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define endl '\n'

using namespace std;

int func(int s, int e, string& str, int flag)
{
	while (s <= e)
	{
		if (str[s] == str[e])
			s++, e--;
		else if (!flag)
		{
			if (func(s, e - 1, str, 1) == 1 || func(s + 1, e, str, 1) == 1)
				flag = 1;
			else
				flag = 2;
			break;
		}
		else
		{
			flag = 2;
			break;
		}
	}

	return flag;
}

int main(void)
{
	FASTIO;

	int t;
	cin >> t;

	while (t--)
	{
		string str;
		cin >> str;
		cout << func(0, str.size() - 1, str, 0) << endl;
	}
	
	return 0;
}