[백준] 회문 17609번 (c++)

출처 : 17609번: 회문 (acmicpc.net)

17609번: 회문

풀이 방법

회문을 판별하는 알고리즘은 쉽게 생각해 낼 수 있다.

하지만 유사회문을 판별을 하는데 조금 생각을 해야 한다.

유사회문은 한 알파벳을 제거했을 때 회문이 되면 유사회문이라고 한다

여기서 유사회문을 판별하는 방법은 문자열을 처음과 끝에서부터 비교해 오면서 

다른 문자가 나올 때 앞쪽 문자를 버릴지 뒤쪽 문자열을 버릴지 판별해주면 된다.

앞쪽 문자를 버리는 경우는 앞쪽 인덱스를 한 칸뒤로 보낸 뒤 뒤쪽문자와 같으면 isPalin함수를 재귀호출을 하는 것이고

뒤쪽 문자를 버리는 경우는 뒤쪽 인덱스를 한칸 앞으로 보낸뒤 앞쪽 문자와 같으면 isPalin함수를 재귀 호출하는 식으로 

작성했다

#include <iostream>
#include <string>

using namespace std;

int isPalin(string str) {
    int ret = 0, str_left = 0, str_right = str.size() - 1, left = 987654321, right = 987654321;
	while (true) {
		// 끝까지 검사를 마친경우
		if (str_left >= str_right) break;
		// 회문아님 확정
		if (ret >= 2) break;
		// 다른 문자나올시 재귀호출
		if (str[str_left] != str[str_right]) {
			ret++;
			// 왼쪽 인덱스 버림
			if (str[str_left+1] == str[str_right]) left = isPalin(str.substr(str_left + 1,str_right - str_left));
			// 오른쪽 인덱스 버림
			if (str[str_left] == str[str_right-1]) 	right = isPalin(str.substr(str_left, str_right - str_left));
			// 둘다 못 버리는 경우
			if (str[str_left+1] != str[str_right] && str[str_left] != str[str_right-1]) return 2;
			ret += min(left, right);
			if (ret > 2) ret = 2;
			return ret;
		}
		str_left++;
		str_right--;
	}
	return ret;
}

int main() {
    int c;
    cin >> c;
    while(c--) {
        string str_in;
        cin >> str_in;
        int result = 0;
        result = isPalin(str_in);
        cout << result << endl;
    }
	return 0;
}