백준 17609번 회문

문제 링크입니다: https://www.acmicpc.net/problem/17609

17609번: 회문

가지치기를 잘해야 하는 문제였습니다.

1. 해당 인덱스가 회문의 조건을 충족할 때는 다음 인덱스로 넘어가고

2. 해당 인덱스가 회문의 조건을 충족하지 않을 경우

i) 현재 인덱스에 있는 문자를 제거한 문자열이 회문을 충족하는지

ii) 혹은 짝을 이루는 인덱스에 위치한 문자를 제거한 문자열이 회문을 충족하는지

 

판별하면 되는 문제였습니다.

 

	#include <iostream>
	#include <string>
	#include <vector>
	#include <cstring>
	using namespace std;
	enum {
	PALINDROME = 0,
	SEMI_PALINDROME,
	NOT_PALINDROME
	};
	int main(void)
	{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int T;
	cin >> T;
	for (int t = 0; t < T; t++)
	{
	string s;
	cin >> s;
	int result = PALINDROME;
	for (int i = 0, j = s.length() - 1; i < j; i++, j--)
	{
	if (s[i] == s[j])
	{
	continue;
	}
	// 문자 하나를 삭제해도 팰린드롬이 아닐 경우
	if (s[i + 1] != s[j] && s[i] != s[j - 1])
	{
	result = NOT_PALINDROME;
	break;
	}
	bool isPalindrome = false;
	// 하나 삭제한 뒤 팰린드롬인지 판별
	for (int k = 0; k < 2 && isPalindrome == false; k++)
	{
	int start = i;
	int end = j;
	k == 0 ? start++ : end--;
	isPalindrome = true;
	for (int a = start, b = end; a < b; a++, b--)
	{
	if (s[a] != s[b])
	{
	isPalindrome = false;
	break;
	}
	}
	}
	result = isPalindrome ? SEMI_PALINDROME : NOT_PALINDROME;
	break;
	}
	cout << result << "\n";
	}
	return 0;
	}

view raw .cpp hosted with ❤ by GitHub

개발환경:Visual Studio 2017

 

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~