취미로 코딩하기

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

이번에 볼 문제는 백준 17609번 문제인 회문이다.
문제는 아래 링크를 확인하자.

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

문자열을 받고, 평범하게 왼쪽부터와 오른쪽부터의 글자를 비교해나가보자.

1) 가운데 글자까지 모든 글자가 일치해나간다면 이 문자열은 회문이다.

2) 처음으로 일치하지 않는 글자가 나온다면

2-1) 왼쪽 글자를 하나 스킵하여 남은 문자열이 회문인지 확인해본다.

2-2) 2-1이 회문이 아니었다면 다시 돌아와서 오른쪽 글자를 하나 스킵하여 남은 문자열이 회문인지 확인해본다.

3) 2에서 하나 건너뛰고 확인한 두 문자열이 모두 회문이 아니라면 2를 출력, 아니라면 1을 출력한다.

위와 같은 알고리즘을 구현하면 선형시간 내에 각 케이스가 회문인지 유사회문인지 아무 것도 아닌지를 판별할 수 있다.

아래는 제출한 소스코드이다.

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

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

	int T; cin >> T;
	while (T--) {
		bool lSkip = 0, rSkip = 0;
		bool chk = 1;
		string s; cin >> s;
		int L = 0, R = s.length() - 1;
		int tempL, tempR;
		while (L < R) {
			if (s[L] == s[R]) {
				L++; R--;
			}
			else if (!lSkip) {
				tempL = L, tempR = R;
				lSkip = 1;
				L++;
			}
			else if (!rSkip) {
				L = tempL, R = tempR;
				rSkip = 1;
				R--;
			}
			else {
				chk = 0;
				break;
			}
		}
		if (chk) {
			if (lSkip) cout << 1 << '\n';
			else cout << 0 << '\n';
		}
		else cout << 2 << '\n';
	}
}