[백준] 17609 회문

 

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

17609번: 회문

 

- 문제요약

입력받은 문자열이 회문인지 유사회문인지 아무것도 아닌지 확인하는 프로그램 작성하기

 

- 첫번째 생각

유사회문 구하는 방법을 우선 모든 문자열의 모든 알파벳을 하나씩 제외시켜보고

회문인지 테스트하는 방법이 있다 생각했는데, 문자열의 길이가 최대 길이인 10만이 되는 경우

10만자의 모든 문자를 하나씩 제외해가면서 회문인지 테스트하는 경우에

시간초과가 예상되어 다른 방법을 고민해봄

 

 

- 두번째 생각

우선 회문인지 확인해보고

회문이 아닌 경우 회문 검사 실패가 뜬 index의 배열
위치 값을 제외한 문자열을 만들어 새로운 문자열에 복사하고

다시한번 회문인지 검사하는 방식으로 생각해보았음

 

 

- 소스코드 (참고하기로 어려울만큼 코드가 지저분하다...)

 

#include<iostream>
#include<cstring>

using namespace std;

int N;
char str[100001], str2[100001];

void copy_str(int exception_idx, int len) {
	int idx = 0;

	for (int i = 0; i < len; i++) {
		if (i == exception_idx) continue;
		str2[idx++] = str[i];
	}
	str2[idx] = '\0';

}

int check_palindrome(int len) {
	for (int i = 0; i < len / 2; i++) {
		if (str[i] != str[len - i - 1]) {
			return i;
		}
	}

	return -1;
}

int check_palindrome2(int len) {
	for (int i = 0; i < len / 2; i++) {
		if (str2[i] != str2[len - i - 1]) {
			return i;
		}
	}

	return -1;
}

int dfs(int depth, int idx) {
	int res;
    
    if (depth >= 2) return 0;

	if (depth == 0) {
		res = check_palindrome(strlen(str));
		if (res == -1) {
			return 0;
		}
		else {
			if (dfs(depth + 1, res) == -1) return 1;
			else return 2;
		}
	}
	else if (depth == 1) {
		copy_str(idx, strlen(str));
		res = check_palindrome2(strlen(str2));
		if (res == -1) return -1;

		copy_str(strlen(str) - idx - 1, strlen(str));
		res = check_palindrome2(strlen(str2));
		if (res == -1) return -1;
		else return 0;
	}

}

int main(void) {
	cin >> N;

	while (N--) {
		cin >> str;
		cout << dfs(0, 0) << '\n';
	}

	return 0;
}