17609번: 회문 - 두 포인터, 재귀

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

17609번: 회문

 

관찰, 알고리즘

일반적인 팰린드롬 문제와 같이 두 포인터를 이용해 index를 좁혀나가면 된다. 이때 주의할 점이 있다.

$$ summums, smummus $$

위 두 문자열과 같이, 두 포인터(\(l, r\))가 가리키는 두 문자가 다른데, \(l+1, r\)와 \(l, r-1\)이 가리키는 두 문자가 같다면 반드시 두 경우 모두 조사해야 한다.

 

답은 0, 1, 2밖에 나오지 않으므로 재귀를 이용해 풀어도 답이 2 이상이 나오면 바로 return하면 되기에 시간 초과가 나지 않는다. 구현이 더러울 수 있기 때문에 깔끔하게 하도록 노력해야 한다.

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef tuple<int, int, int> tiii;

string str;

int solve(int l, int r, int ans)
{
    if (ans == 2)
        return ans;
    if (l > r)
        return ans;

    if (str[l] == str[r])
        return solve(l + 1, r - 1, ans);
    else
    {
        int ret{2};
        if (str[l + 1] == str[r])
            ret = min(ret, solve(l + 2, r - 1, ans + 1));
        if (str[l] == str[r - 1])
            ret = min(ret, solve(l + 1, r - 2, ans + 1));
        return ret;
    }
}

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);

    int T;
    cin >> T;
    while (T--)
    {
        cin >> str;
        cout << solve(0, str.length() - 1, 0) << "\n";
    }
}