[Algorithm]Baekjoon 17609번 :: 회문

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

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
#include <climits>
#include <bitset>
#include <cmath>
#include <mutex>
 
using namespace std;
 
 
int t;
vector<int> answers;
 
 
int IsPalindrome(int leftIndex, int rightIndex, int deleteCount, string& str)
{
    while (leftIndex < rightIndex)
    {
        if (str[leftIndex] != str[rightIndex]) // 일치하지 않을 때
        {
            if (deleteCount == 0) // 삭제할 수 있는기회가 아직 있으면
            {
                if (IsPalindrome(leftIndex + 1, rightIndex, 1, str) == 0 ||
                    IsPalindrome(leftIndex, rightIndex - 1, 1, str) == 0)
                {
                    return 1;
                }
                else
                {
                    return 2;
                }
            }
            else
            {
                return 2;
            }
        }
        else
        {
            ++leftIndex;
            --rightIndex;
        }
    }
 
    return 0;
}
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> t;
 
    for (int i = 0; i < t; ++i)
    {
        string s;
        cin >> s;
 
        answers.push_back(IsPalindrome(0, s.size() - 1, 0, s));
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        cout << answers[i] << endl;
    }
 
    return 0;
}
 
 
 
 
 

 

 

단순히 주어진 문자열이 팰린드롬인지 아닌지를 판별하는게 아니라, 팰린드롬인지, 아니면 한번의 삭제로 팰린드롬을 만들 수 있는지, 혹은 둘 다의 경우가 아닌지를 판별해야하는 문제이다.

 

주어진 문자열자체가 팰린드롬이면 문자열의 양끝에서 가운데까지 체크했을 때, 전부 문자가 일치해야 한다.

만약 일치하지않는게 나왔을 때, 아직 삭제할 수 잇는 기회가 남아있다면 두가지 선택지가 나온다.

왼쪽껄 삭제했다고 가정하고 leftIndex를 ++할지, 아니면 오른쪽껄 삭제했다고 가정하고 rightIndex를 --할지..

 

이 두 재귀탐색에서 하나라도 최종적으로 팰린드롬인게 판별나면 1을 리턴하면 된다.(한번의 삭제로 팰린드롬완성)

만약 이 탐색에서도 팰린드롬이 완성이 안되면 2를 리턴한다. (한번의 삭제를 하더라도 팰린드롬을 미완성)