🖊️ 문제

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

---

🖊️ 풀이

흠.. 문자열이 골드라

처음 보자마자 움 걍 투포인터로 풀면 되겠군?
했는데 나에게 찾아온 반례..
xyyyyxy

즉,
a+1, b와 a, b-1 둘 다 진행할 수 있는 경우가 반례가 생긴다.

내 코드대로 하면 2를 리턴하는데, 답은 1이다.

아래는 실패한 내 1차시도 코드

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

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

	int t;
	cin >> t;

	string input;
	for (int i = 0; i < t; i++) {
		cin >> input;

		int left = 0;
		int right = input.size() - 1;
		int result = 0;
		while (left <= right) {
			if (input[left] == input[right]) {
				left++;
				right--;
			}
			else if (result == 0 && input[left+1] == input[right]) {
				result = 1;
				left += 2;
				right--;
			}
			else if (result == 0 && input[left] == input[right-1]) {
				result = 1;
				left++;
				right -= 2;
			}
			else {
				result = 2;
				break;
			}
		}
		cout << result << '\n';
	}
}

왜냐하면,
나는 left+1 or right-1 둘 중 하나만 탐색했다.
근데 여기서 else를 풀고 한다 쳐도, 실패한 놈이 먼저 리턴되어버린다.

그래서 고민 고민 ......

구글신의 도움을 받았다.
언제쯤 구글신없이 .. 행복할까 ..............

---

그러한 반례를 없애기 위해서는!!

재귀로 끝까지 탐색한다.

어차피 완전한 회문이면 재귀없이 while루프를 돌거고,
삭제는 1번으로 제한되어 있으므로
최악의 경우에도 한 테스트케이스 당 50'000 * 3번의 루프를 돈다.

그래서 그냥 했다.!

첫번째 삭제인 경우에만,
left를 삭제한 경우 / right를 삭제한 경우 두 가지를 모두 끝까지 검사한다.
그래서 둘 중 하나라도 성공하면 유사회문.
아니라면 회문아님.

휴,,
재귀는 생각도 못해따.

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

string input;
int flag;

int isPalindrome(int a, int b) 
{
	while (a < b) {
		if (input[a] == input[b]) {
			a++;
			b--;
		}
		else if (flag == 0) {
			flag = 1;
			if (isPalindrome(a + 1, b) == 0 || isPalindrome(a, b - 1) == 0)
				return 1;
		}
		else return 2;
	}
	return 0;
}

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

	int t;
	cin >> t;

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