[백준 17609] 회문 (C++)

처음 고민했던 사고과정과 이후 정답풀이를 같이 정리해 놓았다. 

1. 문제

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

17609번: 회문

2. 풀이

시행 착오

회문의 특징을 살펴본 결과 좌우대칭이었다. 이를 고려해서 생각해보았다.

1) 문자열의 길이가 홀수일 경우

가운데를 제외한 모든 문자는 왼쪽에 존재한다면 오른쪽에도 반드시 존재해야 하므로 가운데를 제외한 문자의 수는 짝수개이다.

2) 문자열의 길이가 짝수일 경우

좌우대칭이므로 모든 문자의 수가 짝수개이다.

 

하지만 이렇게 경우를 하나하나 고려할 경우 문제가 생긴다.

1. 단순히 두 가지 경우로 나누어 해결하기에는 확인하기 어려운 예외가 많을 수 있다.
2. 설령 해결한다고 하더라도 스파게티 코드가 될 가능성이 높다.
3.  문자열의 개수를 각각 세는 과정에서 시간복잡도가 O(n제곱)이상으로 넘어간다.

 

따라서 문제의도를 다시 생각해볼 필요가 있다.

---

정답 풀이

시간복잡도를 고려해 볼 때 무조건 한 번의 탐색에서 모두 끝내야 한다!!

유사 회문의 경우에서 문자열의 탐색과정을 살펴보자.

[입력 예시]

a   b   c   x   c   k   b   a

길이 length: 8

문자를 비교하는 두 포인터 left: 0, right: 7

 

(left < length / 2)인 조건에서 계속 탐색해야 한다. (두 포인터 모두 int형이므로 길이가 홀수일 때에도 성립)

• 같은 문자가 나올 경우
  가운데를 기준으로 양쪽 문자열을 비교하며 탐색한다.
  같으면 계속 다음문자열로 넘어가며 다른 문자열이 나올 때까지 비교한다.
  만약 문자열의 절반까지 모두 탐색했는데 같다면 회문이다.

 a   b   c   x   c   k   b   a    →   left = 0, right = 7
↑                             ↑

 a   b   c   x   c   k   b   a   →   left = 1, right = 6
     ↑                   ↑

• 다른 문자가 나올 경우
  left또는 right의 문자 중에서 하나를 제외하고 계속 탐색해야 한다. 
  현재 condiction을 그대로 유지하고 같은 작업을 반복해야 하므로 재귀함수로 함수를 다시 실행해할 수 있다.

 a   b   c   x   c   k   b   a   →   left = 2, right = 5
         ↑           ↑

1st) 먼저 left를 제외하고 다음 탐색을 진행한다.

               그러면 다음과 같이 또 다른문자가 나온다.               

 a   b   c   x   c   k   b   a   →   left = 3, right = 5
              ↑      ↑

이미 문자를 한 번 넘겼는데 또 한번 문자를 넘기면 재귀함수가 2번 호출되므로 회문도 유사회문도 아닌 경우이다.

 

2nd) 다음으로 right를 제외하고 다음 탐색을 진행한다.

 a   b   c   x   c   k   b   a   →   left = 3, right = 4
          ↑      ↑  

문자를 한 번 넘기고 탐색한 결과 (left < length / 2) 의 범위까지 모두 같으면 유사 회문이다. 이 경우는 재귀함수가 1번 호출되었다.

 

따라서 재귀함수로 구현하고 회문인지, 유사회문인지, 둘 다 아닌지는 끝나고 재귀함수의 호출 순서로 결정한다.

이를 정리하면 다음과 같다.

 

1. 양쪽 문자를 비교하며 탐색한다.
2. 탐색이 끝날 때까지 모두 같으면 회문이다.
3. 다른 문자가 나올 경우 왼쪽 또는 오른쪽 문자열을 넘기고 현재의 left, right를 이어받아 재귀 함수를 실행하여 다시 탐색한다.
4. 1번째 호출된 재귀함수에서 모두 같으면 유사회문이고 다시 다른 문자가 나와서 재귀함수가 2번째 실행되면 둘 다 아닌 경우이다.

이 과정에서 현재의 condiction을 유지하고 같은 작업을 반복할 때 재귀함수를 실행하면 매우 효율적이다.

3. 코드

#include<iostream>
#include<string>
using namespace std;

string a;
int cnt = 0;

int isPalindrom(int left, int right, int cnt) {
	if (cnt == 2) return 2;

	while (left < right) {
		if (a[left] == a[right]) {
			left++;
			right--;
		}
		else {
			if (isPalindrom(left + 1, right, cnt + 1) == 2 && isPalindrom(left, right - 1, cnt + 1) == 2) {
				return 2;

			}
			else return 1;
		}

	}

	if (cnt == 0) return 0;
	else return 1;

	
}

int main(void) {
	cin.tie(0);
	ios::sync_with_stdio(false);

	int T;
	int left, right;
	cin >> T;
	while (T--) {
		cin >> a;
		left = 0;
		right = a.length() - 1;

		cout << isPalindrom(left, right, cnt) << "\n";

	}
	return 0;
}

4. 참고

펠린드롬수를 판별하는 알고리즘은 기본적인 팰린드롬수의 알고리즘을 참고하면 도움이 된다.

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

1259번: 팰린드롬수