[백준/C++] 17609 회문

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

코드

#include <iostream>
using namespace std;

#define FASTIO ios::sync_with_stdio(false); cin.tie(NULL);
int t;
string s;

int makePal(int left, int right, bool isUse) {
	while (left < right) {
		if (isUse && s[left] != s[right])
			return 2;

		if (s[left] == s[right]) {
			left++;
			right--;
		}
		else {
			if (makePal(left + 1, right, true) == 0 || makePal(left, right - 1, true) == 0)
				return 1;
			else return 2;
		}
	}
	return 0;
}

int main() {
	FASTIO;
	cin >> t;
	while (t--) {
		cin >> s;
		cout << makePal(0, s.length()-1, false) << "\n";
	}
	return 0;
}

설명

아이디어는 다음과 같다.

 

left는 맨 왼쪽, right는 맨 오른쪽에서 출발해서 가운데로 각자 이동한다. s[left] == s[right]이면 회문 조건을 충족하는 것이니 계속 가운데로 이동시킨다. 만약 s[left] != s[right] 라면 회문이 아니다. 다만 유사회문일 가능성이 있으므로 left를 한 번 더 이동시키거나, right를 한 번 더 이동시켜주고 isUse를 true로 바꾼다. 이때부터 다시 위의 상황을 반복하는데 이미 회문이 아니므로 s[left] != s[right] 이면 일반 문자열이다. 

 

이를 계속 반복해주고 상황에 맞는 반환값을 리턴한다.

 

 

느낀 점

아래처럼 코드를 짜서 한 번 틀렸다.

    while (t--) {
		cin >> s;
		bool flag = true, getAns = false;
		left = 0, right = s.length() - 1;

		while (left < right) {
			if (!flag && s[left] != s[right]) {
				cout << 2 << "\n";
				getAns = true;
				break;
			}

			if (s[left] == s[right]) {
				left++;
				right--;
			}
			else {
				if (left + 1 < right && s[left + 1] == s[right]) {
					right--;
					left += 2;
					
				}
				else if (right - 1 > left && s[right - 1] == s[left]) {
					left++;
					right -= 2;
				}
				flag = false;
			}
		}

		if (!getAns && flag) cout << 0 << "\n";
		else if (!getAns && !flag) cout << 1 << "\n";
	}

 이유는 투포인터 부분에서 else 내에서 if 와 else if가 같은 상황에서 실행되었어야 하는데 그렇지 못해서였다. 그래서 left, right를 이동시키는 투 포인터 파트 자체를 함수로 뽑아냈다. 

 

이렇게 하니 바로 통과했다! 아이디어 자체는 어렵지 않았던 것 같다.