문제

나의 요약

회문: 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열
유사 회문: 한 문제를 삭제하여 회문으로 만들 수 있는 문자열
주어진 문자열이 회문인지, 유사 회문인지, 둘다 아닌지 0, 1, 2로 출력하자.

접근 방법

문자열의 시작과 끝에서 검사하며 각각 오른쪽, 왼쪽으로 나아간다.
두 문자가 같은지 조사한다. 같다면 계속해서 나아가, 중앙까지 나아갔다면 회문으로 마무리한다.
만약 같지 않은 경우가 있다면, 그 상황에서 끝의 포인터가 한칸 왼쪽으로 나아간 경우, 혹은 시작의 포인터가 한칸 오른쪽으로 나아간 경우를 다시 회문 검사한다.
여기서 중앙까지 나아갔다면 유사 회문인 것이고, 나아가다가 또 다른 문자가 있다면 둘다 아닌 것이다.

풀이

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

int T;
vector<string> strs;

void Input()
{
    cin >> T;
    strs.resize(T);
    for (int i = 0; i < T; i++)
    {
        cin >> strs[i];
    }
}

bool IsPalindrome(int& left, int& right, int strIdx)
{
    while(left < right)
    {
        if(strs[strIdx][left] != strs[strIdx][right])
        {
            return false;
        }
        left++; right--;
    }
    return true;
}

void Solve()
{
    for(int i = 0; i < T; i++)
    {
        int len = strs[i].length();
        int left = 0, right = len - 1;
        int ans = 0;

        if(!IsPalindrome(left, right, i))
        {
            int newLeft = left+1, newRight = right;
            if(IsPalindrome(newLeft, newRight, i))
            {
                ans = 1;
            }
            else if(IsPalindrome(newLeft=left, newRight=right-1, i))
            {
                ans = 1;
            }
            else
            {
                ans = 2;
            }
        }
        
        cout << ans << '\n';
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Solve();
}

IsPalindrome 함수는 주어진 left와 right에서 한칸씩 나아가며 두 포인터가 만날 때까지 팰린드롬인지 조사하는 함수이다. 여기서 left와 right는 레퍼런스 변수를 인자로 받아, 어디서 끝났는지 호출한 부분에서 알 수 있다.
Solve 함수에서는 한번 IsPalindrome 함수를 진행해 그냥 회문인지 판단하고, 아니라면 멈춘 left와 right를 토대로 left+1, right로 다시 진행, 또한 left, right-1로 다시 진행한다. 여기서 회문이라면, 유사 회문으로 판단한다. 여기서도 회문이 아니라면 아무것도 아닌 2를 출력하면 된다.

회고

이 문제 또한 4년전에 풀었던 문제였다. 4년과 똑같은 실수를 처음에 저질렀는데, 유사 회문을 조사할 때 회문을 통째로 조사한 것이 아니라, 회문이 실패한 구간에서 left+1와 right의 문자가 같다면, 혹은 left와 right-1의 문자가 같다면 유사 회문이라고 판단했다. 이는 판단하는 순서에 따라 XYXYAAYXY, 혹은 YXYAAXYXY 같은 문자열이 있다면 자칫 아무것도 아니라고 판단할 수도 있는 방법이었다.
따라서 유사 회문을 판단할 때 다시 한번 회문 판단하는 방법을 택했다. 4년전과 같은 실수를 반복하는 걸 보니 역시 꾸준히 반복하는 게 중요한 것 같다. 작동 시간 자체는 더 줄어서 다행이었다.