(C++) - 백준(BOJ) 17609번 : 회문

www.acmicpc.net/problem/17609

17609번: 회문

재쉬를 이용해 푼 문제였습니다.

 

 

풀이방법

 1. 분류기 함수를 만듭니다. 펠린드롬이면 0, 유사 펠린드롬이면 1, 이외의 경우엔 2를 반환하는 함수입니다.

 2. 유사 펠린드롬인지 확인합니다 : left, right번째 문자를 확인하며 펠린드롬 여부를 결정합니다.

left번째 right번째 문자열이 같다면 left +1, right -1 문자를 확인합니다.

아닌 경우 : 지울 문자열을 선택합니다. left번째 문자를 지우거나 right번째 문자를 지웁니다.

left가 right을 초과하면 회문이므로 1를 반환합니다.

 3. 답을 출력합니다.

 

Code

#include <bits/stdc++.h>
using namespace std;
int t;
string s;

int isPalin(string s){
    for(int i = 0; i < s.size()/2; i++)
        if(s[i] != s[s.size() - 1 - i]) 
            return 0;
    return 1;
}

int nearPalin(int left,int right,bool skip){
    if(left > right) return 1;
    if(s[left] == s[right]) return nearPalin(left+1,right-1,skip);
    if(!skip) return max(nearPalin(left+1,right,1),nearPalin(left,right-1,1));
    else return 0;
}

int classifier(string s){
    if(isPalin(s)) return 0;
    if(nearPalin(0,s.size()-1,0)) return 1;
    return 2;
}

int main(){
    cin >> t;
    while(t--){
        cin >> s;
        cout << classifier(s)<< '\n';
    }

}