백준 17609 - 회문 (C++)

 

 

주어지는 문자열이 회문인지, 유사회문인지 혹은 아무것도 아닌지 판별하는 문제이다.

 

aabbaa 처럼, 뒤집어도 기존과 같은 문자열이라면 회문이다.

aabbcaa 처럼, 그냥은 회문이 아니지만 문자 하나(c)를 제거한다면 회문이 되는 경우는 유사 회문이다.

abcde 처럼, 회문도 유사회문도 아닌 경우는 아무것도 아니다.

 

회문은 0, 유사회문은 1, 아무것도 아니라면 2를 출력하면 되는 문제이다.

 

문제 풀이

 

본인은 재귀함수와 투포인터를 사용하여 풀었다.

문자열을 뒤집어도 기존과 같다는 의미는, 맨 앞으로부터 일정 거리에 있는 문자와 맨 끝으로부터 일정 거리에 있는 문자가 동일하다는 뜻이다.

 

그림처럼, 회문이라면 초록색 화살표가 가리키는 것처럼 양 끝의 문자가 같아야 하고 양 끝으로부터 1씩 떨어진 주황색 화살표가 가리키는 문자도 동일해야 한다.

 

이를 검사하기 위해 투포인터를 사용하였다.

Left는 1씩 증가시키고, Right는 1씩 감소시키면서 Left와 Right가 가리키는 문자가 동일한지를 검사하여 회문 여부를 검사하였다.

 

하지만, 유사 회문을 검사하기 위해선 위의 방법만으로는 검사할 수 없다.

유사 회문의 경우엔 이상한 문자가 하나 중간에 끼어있기 때문이다.

 

하지만, 유사 회문에서도 문자 하나를 제거한다면 회문이 되기 때문에 이를 이용하요 동일한 방식에 조건 하나만 추가해주었다.

맨 처음에, 주황색 화살표는 각각 c와 b를 가리키고 있다.

서로 다른 문자를 가리키고 있는 상황이다.

이 때, Left + 1은 Right가 가리키는 문자와 같은가를 검사하였다.

유사회문이라면 c를 제거하였을 때, 회문이 되어야 한다.

그러므로 c의 다음 문자는 Right가 가리키는 문자와 동일해야 한다.

Left+1 과 Right가 가리키는 문자가 동일하다면 DeleteCount를 1 증가시켰다.

 

문자열의 처음과 끝을 모두 탐색할 때까지 DeleteCount가 1이라면 유사회문이라고 판정하였다.

(문자를 2개 이상 제거해야 회문이 된다면 유사 회문이 아니기 때문이다.)

 

반대로, Right쪽에 제거해야할 문자가 있을 수도 있기 때문에 Left와 Right - 1에 대해서도 동일한 검사를 해주었다.

 

그런데, 이 상황에서도 예외가 한가지 있다.

보면, Left와 Right가 다른 값임을 알 수 있다.

이 상황에서 Left를 제거하였다고 가정했을 때 Left + 1과 Right가 동일하기 때문에 Left를 제거하게 될 것이다.

하지만, Left를 제거한다면 yyyxy가 되어 회문이 되지 않는다. 왜일까?

 

Right또한 제거할 수 있는 경우이기 때문이다.

Right를 제거하였다고 가정했을 때 Left와 Right - 1 또한 동일하기 때문에 Right또한 제거할 수 있다.

 

즉, Left + 1 == Right 이면서 동시에 Left == Right - 1인 경우엔 두 경우에 대해 모두 검사를 해보아야 하는 것이다.

이 때문에 본인은 재귀함수를 이용하여 문제를 해결하였다.

 

코드 풀이

 

 

int NumOfCase = 0;
std::cin >> NumOfCase;

std::vector<int> Answer(NumOfCase, 0);

 

먼저, 테스트케이스의 수를 입력받았고 그 크기만큼 정답을 저장해줄 배열을 Resize해주었다.

 

for (int i = 0; i < NumOfCase; i++)
{
    std::string CurStr;
    std::cin >> CurStr;

    int Left = 0;
    int Right = CurStr.size() - 1;

    int DeleteCount = Solution(CurStr, Left, Right, 0);

    Answer[i] = std::min(DeleteCount, 2);
}

 

이후, 입력받는 문자열에 대해 Solution이라는 함수를 실행해주었고, 결과값을 Answer에 저장해주었다.

Solution함수 내부를 보자.

 

int Solution(const std::string& _Str, int _Left, int _Right, int _DeleteCount)
{
    if (_Left > _Right)
    {
        return _DeleteCount;
    }

    if (_DeleteCount >= 2)
    {
        return 2;
    }

    if (_Str[_Left] != _Str[_Right])
    {
        if (_Str[_Left + 1] == _Str[_Right] && _Str[_Left] == _Str[_Right - 1])
        {
            int Answer_1 = Solution(_Str, _Left + 1, _Right, _DeleteCount + 1);
            int Answer_2 = Solution(_Str, _Left, _Right - 1, _DeleteCount + 1);

            return std::min(Answer_1, Answer_2);
        }
        else if (_Str[_Left + 1] == _Str[_Right] && _Str[_Left] != _Str[_Right - 1])
        {
            return Solution(_Str, _Left + 1, _Right, _DeleteCount + 1);
        }
        else if (_Str[_Left + 1] != _Str[_Right] && _Str[_Left] == _Str[_Right - 1])
        {
            return Solution(_Str, _Left, _Right - 1, _DeleteCount + 1);
        }
    }
    else
    {
        return Solution(_Str, _Left + 1, _Right - 1, _DeleteCount);
    }
}

 

먼저, 투포인터 방식이기 때문에 _left가 _Right보다 커질 때 재귀함수를 return하도록 하였다.

또한, _DeleteCount가 2이상이라면 어차피 회문도 유사회문도 아니므로 더 검사할 필요 없이 바로 종료해주었다.

 

그 다음을 보면, Left와 _Right가 가리키는 값이 같다면, Left + 1, _Right - 1에 대해 검사해주고 있다.

만약, 다르다면 왼쪽과 오른쪽중 제거할 수 있는 문자를 판단한 뒤, 해당 문자를 제거해주었다.
(실제로 제거한 것은 아니고, 투 포인터가 가리키는 위치만 바꿔서 제거한 것과 유사한 느낌을 구현하였다.)

 

 만약, 왼쪽 문자와 오른쪽 문자 모두 제거할 수 있는 문자라면 양쪽에 대해 DeleteCount를 모두 검사해준 뒤, 둘 중 더 작은 쪽으로 반환해주었다.

 

이 함수가 끝나면, 문자열을 돌면서 문자를 몇개 제거했는가를 반환하게 된다.

만약 0이라면 회문이고, 1이라면 유사회문이며, 2라면 아무것도 아닌 것이다.

 

모든 테스트케이스에 대해 Solution 함수를 호출한 뒤, 마지막으로 답을 출력해주면 끝이다.

for (int i = 0; i < Answer.size(); i++)
{
    std::cout << Answer[i] << "\n";
}

 

 

코드 전문

#include <iostream>
#include <vector>

void Init()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);
}

int Solution(const std::string& _Str, int _Left, int _Right, int _DeleteCount)
{
    if (_Left > _Right)
    {
        return _DeleteCount;
    }

    if (_DeleteCount >= 2)
    {
        return 2;
    }

    if (_Str[_Left] != _Str[_Right])
    {
        if (_Str[_Left + 1] == _Str[_Right] && _Str[_Left] == _Str[_Right - 1])
        {
            int Answer_1 = Solution(_Str, _Left + 1, _Right, _DeleteCount + 1);
            int Answer_2 = Solution(_Str, _Left, _Right - 1, _DeleteCount + 1);

            return std::min(Answer_1, Answer_2);
        }
        else if (_Str[_Left + 1] == _Str[_Right] && _Str[_Left] != _Str[_Right - 1])
        {
            return Solution(_Str, _Left + 1, _Right, _DeleteCount + 1);
        }
        else if (_Str[_Left + 1] != _Str[_Right] && _Str[_Left] == _Str[_Right - 1])
        {
            return Solution(_Str, _Left, _Right - 1, _DeleteCount + 1);
        }
    }
    else
    {
        return Solution(_Str, _Left + 1, _Right - 1, _DeleteCount);
    }
}

int main()
{
    Init();
    int NumOfCase = 0;
    std::cin >> NumOfCase;

    std::vector<int> Answer(NumOfCase, 0);
    for (int i = 0; i < NumOfCase; i++)
    {    
        std::string CurStr;
        std::cin >> CurStr;

        int Left = 0;
        int Right = CurStr.size() - 1;

        int DeleteCount = Solution(CurStr, Left, Right, 0);

        Answer[i] = std::min(DeleteCount, 2);
    }

    for (int i = 0; i < Answer.size(); i++)
    {
        std::cout << Answer[i] << "\n";
    }

    return 0;
}