백준17609 회문

작성일 | In

문제 출처

  • 2019 KOI 1차 초등부 2번

시간복잡도

  • O(N)

풀이

문자열이 주어졌을 때 회문인지 판단하는 것은 O(N)에 할 수 있습니다.

한 글자를 제거했을 때 회문인지 판단하는 것을 O(N)에 처리하는 방법을 생각해봅시다.
먼저, 회문은 양쪽 끝에 각각 l, r이라는 포인터를 잡은 뒤, 한 칸 씩 안쪽으로 이동하며 비교해서 판별합니다. l과 r이 가리키는 문자가 한 번이라도 다른 경우가 생기면 회문이 아닙니다.
이 방식을 이용해서 한 글자만 제거했을 때 회문인지 아닌지 판단할 수 있습니다.

전체 문자열은 회문이 아니면서 한 글자를 제거했을 때 회문이라면 당연히 l, r이 가리키는 문자가 다른 경우가 발생합니다.
summuus, xabba의 경우에는 각각 굵은 글씨로 표시된 부분에서 두 문자가 서로 다릅니다.
summuus에서 굵은 글씨로 표시된 u를 제외하면 회문이 됩니다.
같은 방법으로 xabba에서 굵을 글씨로 표시된 a를 제외하면 회문이 됩니다.

위에 있는 두 예시를 통해서 처음으로 l과 r이 다른 문자를 가리킬 때, l이 가리키는 문자 혹은 r이 가리키는 문자를 제거해서 회문이면 1을 출력하면 된다는 것을 알 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
#include <bits/stdc++.h>
using namespace std;

bool isPal(string &s){
	int l = 0, r = s.size() - 1;
	while(l < r){
		if(s[l] != s[r]) return 0;
		l++; r--;
	}
	return 1;
}

void solve(){
	string s; cin >> s;
	if(isPal(s)){
		cout << "0\n"; return;
	}
	int l = 0, r = s.size() - 1;
	while(1){
		if(s[l] != s[r]) break;
		l++; r--;
	}
	string a, b;
	for(int i=0; i<s.size(); i++){
		if(i != l) a += s[i];
		if(i != r) b += s[i];
	}
	if(isPal(a) || isPal(b)) cout << "1\n";
	else cout << "2\n";
}

int main(){
	ios_base::sync_with_stdio(0); cin.tie(0);
	int t; cin >> t;
	while(t--) solve();
}