[백준 17609] 회문

백준 17609번 : 회문

www.acmicpc.net/problem/17609

17609번: 회문

 

---

/* 문제 설명 */

문자열이 입력으로 주어질 때, 이를 분석하여

0. 회문 : 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열

1. 유사 회문 : 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열

2. 회문도, 유사 회문도 아닌 것

셋 중 무엇인지 출력하라.

 

 

/* 해결 방안 */

현재 보고 있는 글자를 삭제하는 경우와 유지하는 경우에 대해 따져봐야한다.

→ 이를 쉽게하기 위해 함수를 이용하자!

0	1	2	3	4	5	6
m	a	d	e	d	a	m

회문 특성 상, 인덱스 0과 6은 페어고 1과 5는 페어다.

만약 1번 위치를 보고 있는데, 얘를 삭제하는 경우에는 2와 5를 비교해줘야한다.

또한, 만약 5번 위치를 보고 있는데, 얘를 삭제하는 경우에는 1과 4를 비교해줘야한다.

 

따라서 func(int st, int en, bool flag)에서 st와 en를 잘 조정하여 탐색을 하자.

bool flag는 문자를 삭제했는지 여부를 담고 있어, 유사 회문인지 그냥 회문인지를 구별해준다.

 

/* 구현 과정 */

1. 0과 n-1에 대해서 함수를 호출한다.

2. 만약 두 페어의 값이 같다면 넘어간다.

3. 두 페어의 값이 다르다면, 삭제하는 경우와 유지하는 경우에 대해 분기를 나눠가며 함수를 수행한다.

4. bool flag로 유사회문인지 그냥 회문인지 확인한다.

5. aaaaa와 같이 유사회문이면서 그냥 회문인 경우도 있기 때문에, 이 점을 잘 생각하며 ans 값을 지정한다.

 

/* 소스 코드 */

#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define mod 10007
typedef long long ll;
typedef pair<int, int>pi;
typedef pair<int, pi>pii;

int tc, len, ans;
string str;

void func(int st, int en, bool flag) {
	if (st >= en) {
		if (flag) ans = min(ans, 1);
		else ans = 0;
		return;
	}

	if (str[st] == str[en]) func(st + 1, en - 1, flag);
	else {
		if (flag) return;
		else {
			func(st + 1, en, 1);
			func(st, en - 1, 1);
		}
	}
}

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

	cin >> tc;
	while (tc--) {
		cin >> str;
		ans = 2;
		len = str.length();

		func(0, len - 1, 0);
		cout << ans << "\n";
	}
}

 

/* 얻어갈 점 */

반복문을 써서 직접 구현하는 것보단, 함수를 이용하여 탐색을 하는 것이 훨씬 간편할 때가 많다.

특히 분기를 나눠서 탐색해야하는 경우에는 함수를 쓰자!

 

 

---