백준 / 17609 / 회문 / C++

문제 링크 : https://www.acmicpc.net/problem/17609

#include <bits/stdc++.h>

using namespace std;

int ans = 0;

int check(string &str, int left, int right, int delcount)
{
    if (left >= right)
    {
        if (delcount == 0)
        {
            return 0;
        }
        else
        {
            return 1;
        }
    }
    if (str[left] != str[right])
    {
        if (delcount == 0)
        {
            return min(check(str, left, right - 1, 1), check(str, left + 1, right, 1));
        }
        return 2;
    }
    else
    {
        return check(str, left + 1, right - 1, delcount);
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    //freopen("test.txt", "rt", stdin);
    int n;
    cin >> n;
    while (n--)
    {
        string temp;
        cin >> temp;
        cout << check(temp, 0, temp.length() - 1, 0) << "\n";
    }
    return 0;
}

회문 / 유사회문 판정 자체는

• start 인덱스와 end 인덱스 투 포인터 로직
• 유사회문 판정을 위한 delcount를 인자로 넘겨주는 재귀 함수 로직

을 통해 처리할 수 있었다. 완벽하게 구현했다고 생각해서 제출했더니... 99%에서 오답이 떴다...

기존 코드에 대한 반례를 찾다 보니 유사회문 판정을 위한 한칸 뛰어넘기 후 바로 if (left >= right) 로직에 걸리는 경우(ex."abca")에 대한 예외 처리가 필요했다. 그래서 로직을 변경해

min(check(str, left, right - 1, 1), check(str, left + 1, right, 1));

라는 return값을 만들어 처리했고, 결과는 AC를 받았다

로직 자체는 금방 생각해냈지만 끝마무리에서 유독 애를 먹은 문제였다...