백준 17609번 C++ 풀이

문제

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

시간 제한	메모리 제한	solved.ac 티어
1초(추가 시간 없음)	512MB	골드 5

---

풀이

 밀린 문제이다. 일반적인 회문은 원래 문자와 뒤집은 문자가 같은 것을 의미하지만, 해당 문제에서는 유사 회문이라는 개념을 제시한다. 유사회문이란 원래 회문은 아니지만 문자를 단 한개를 지웠을 때 회문이 되는 문자를 의미한다. 이 문제에서는 어떤 문자가 회문인지, 유사회문인지, 그것도 아닌지 모두 판단해보는 문제이다.

 

 일반적인 회문 판단은 풀이할 필요가 없을 듯하니, 코드를 바로 읽어보면 될 것 같다. 우리가 중요하게 봐야하는건 유사회문 판별이다. 일반적인 회문처럼 문자열의 맨 앞과 맨 뒤를 검사하되, 중간에서 다른 문자를 만날수도 있을 것이다. 하지만 어떤 문자를 지워야할지는 알 수 없다. 그러니 앞에 있는 다른 글자도 지워보고, 뒤에 있는 다른 글자도 지워본다. 이때 우리는 문자를 하나 지웠기 때문에 지워서 넘어왔는지 여부를 같이 넘겨주어 판단해본다.

코드1

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

string str;

bool isPalindrome() {
	for(int i = 0; i < str.length() / 2; i++) {
		if (str[i] != str[str.length() - 1 - i]){
			return false;
		}
	}
	return true;
}

bool isPseudoPaildrome(int i = 0, int l = 0, int r = 1, bool del_flag = false) {
	for(; i < str.length() / 2; i++) {
		if (str[i + l] != str[str.length() - r - i]){
			if (del_flag) {
				return false;
			}
			else {
				return isPseudoPaildrome(i, l+1, r, true) ||
					isPseudoPaildrome(i, l, r+1, true);
			}
		}
	}
	return true;
}

void sol() {
	int r;
	if (isPalindrome()) {
		r = 0;
	}
	else if (isPseudoPaildrome()) {
		r = 1;
	}
	else {
		r = 2;
	}
	cout << r << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	int tc; cin >> tc;
	while(tc--) {
		cin >> str;
		sol();
	}
}

---

 위 코드는 사실 24년 9월 4일에 제출한 코드이고, 이 글을 쓰는 현재 시점은 25년 1월 19일이다. 코드를 지금 다시 보며 든 생각이 회문과 유사회문을 판단하는 함수를 굳이 나눌 필요가 없어보인다. 유사회문을 판단하는 isPseudoPaildrome 함수를 맨 처음 호출할때무터 삭제하고 넘어왔다고 거짓말을 하면 넘겨주면 회문을 판단하는 것과 같아진다. 다만 함수의 매개변수 순서를 조금 수정해주었다.

코드2

#include <bits/stdc++.h>
#define endl '\n'
using namespace std;

string str;

bool isPseudoPaildrome(bool del_flag = false, int i = 0, int l = 0, int r = 1) {
	for(; i < str.length() / 2; i++) {
		if (str[i + l] != str[str.length() - r - i]){
			if (del_flag) {
				return false;
			}
			else {
				return isPseudoPaildrome(true, i, l+1, r) ||
						isPseudoPaildrome(true, i, l, r+1);
			}
		}
	}
	return true;
}

void sol() {
	int r;
	if (isPseudoPaildrome(true)) {
		r = 0;
	}
	else if (isPseudoPaildrome()) {
		r = 1;
	}
	else {
		r = 2;
	}
	cout << r << endl;
}

int main() {
	cin.tie(0)->sync_with_stdio(false);
	int tc; cin >> tc;
	while(tc--) {
		cin >> str;
		sol();
	}
}