백준 17609: 회문

문제 요약

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다.

문제 분류

• 문자열
• 두 포인터

문제 풀이

주어진 문자열을 탐색하기 위해 두 변수 i와 j를 선언하고, i는 0부터, j는 s.length() - 1부터 탐색한다.

s[i] == s[j]라면 양 단의 문자가 같은 것이므로 i++ 및 j--를 수행한다. 이런식으로 회문임을 파악하는데, 둘이 다를 경우에는 다음과 같다.

우선 유사회문인지 파악해야하는데, i쪽의 문자를 지워야 할지, j쪽의 문자를 지워야 할지 모르므로 두 경우 모두 파악한다. 즉, i + 1~j의 문자열이 회문인지, i~j + 1의 문자열이 회문인지 검사하고, 둘 중 하나라도 회문이라면 유사회문으로 파악한다.

둘 다 회문도 아니라면 그 외의 경우로 출력하면 된다.

풀이 코드

#include <stdio.h>
#include <iostream>
#include <algorithm>

using namespace std;

string s;

bool isPal(int i, int j)
{
	while (i < j) {
		if (s[i] == s[j]) {
			i++;
			j--;
		}
		else return false;
	}
	return true;
}

int main()
{
	int t, i, j, res;
	cin >> t;
	while (t--) {
		cin >> s;
		res = 0;
		for (i = 0, j = s.length() - 1; i < j;) {
			if (s[i] == s[j]) {
				i++;
				j--;
			}
			else {
				if (isPal(i + 1, j) || isPal(i, j - 1))
					res = 1;
				else 
					res = 2;
				break;
			}
		}
		cout << res << "\n";
	}
	return 0;
}