[Beakjoon] 17609 회문 (C++)

문제 링크

BOJ 17609 : 회문

문제

풀이

회문 판별 문제인데, 유사회문이라는 개념이 등장한다.
유사회문이란 1개의 문자를 제거했을 때 회문이 되는지 확인하는 문제이다.

회문판별은 간단한데, 유사회문이 될 수 있는지 여부를 어떻게 판별해야하는지 생각이 필요했다.

만걍 S[i] != S[j] 인 경우 유사회문이 되는 경우는 S[i]나 S[j]둘 중 하나를 제거했을 때 해당 문자열이 회문이 되는 경우이다.

이것을 재귀로 작성하면 간단한데, 재귀를 떠올리지 못 해서 어떻게 케이스를 나눠야할지 한참 삽질을 했다.

그리디 분류에서 문제를 봐서 재귀 알고리즘이 사용될 거라고 생각하지 못했다.
사용되는 알고리즘들에 대해 조금 더 입체적으로 사고할 수 있어야 할 것 같다.

코드

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <vector>
#include <algorithm>

#define endl "\n"

using namespace std;

int N;

int isPalindrome(string s, int l, int r, bool skipCnt){

    while(l<r){
        if(s[l] == s[r]){l++; r--;}
        else if(skipCnt){
            skipCnt = false;
            if(isPalindrome(s, l+1, r, false)==0 || isPalindrome(s, l, r-1, false)==0) return 1;
        }
        else return 2;
    }

    return 0;
}

void Solve() {
    string s;
    cin>>s;
    cout<<isPalindrome(s, 0, s.size()-1, true)<<endl;

}


int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T; cin>>T;
    while(T-->0) Solve();

    return 0;
}