[백준][C++] 17609 회문

17609. 회문

17609번: 회문

문제 풀이

GitHub - minyoung529/AlgorithmStudy: 여러 알고리즘 문제를 푸는 저장소입니다.

회문은 껌이라고 생각한 나에게... 유사 회문이란 시련을 준 문제. 첫 접근을 애매하게 잘해서 문제가 되었다.

 

처음 알고리즘 설계는...

 

1. 두 포인터가 문자열의 중심에서 가까워지며 양 끝이 같은지 검사한다.
2. 두 포인터의 값이 같지 않다면...만약 같다면 검사한 쪽의 포인터를 문자열에서 없애준다. 없애주면 회문이 될 수도 있으므로!
3. 왼쪽 포인터는 오른쪽 - 1의 값과 같은지, 오른쪽 포인터는 왼쪽 + 1과 같은지 검사한다.
4. 두 포인터의 값이 같지 않고, 2를 2번 이상 반복하면 유사 회문이 아니다.

 

글로 쓰니 이해가 안 돼서, 그림으로 가져왔다!

#include<iostream>
using namespace std;

int main()
{
    int testCnt;
    cin >> testCnt;

    while (testCnt--)
    {
        string input;
        int exIndex = -1;
        int palindrome = 0;
        cin >> input;

        for (int i = 0; i < input.size() / 2 + 1; i++)
        {
            int ri = input.size() - i - 1;

            if (palindrome >= 2)break;
            if (input[i] == input[ri])continue;

            if (input[i] == input[ri - 1] || input[ri] == input[i + 1])
            {
                if (input[i] == input[ri - 1])
                    exIndex = ri;
                else
                    exIndex = i;

                input.erase(input.begin() + exIndex);
                i = 0;
                palindrome++;
            }
            else
            {
                palindrome = 2;
            }
        }

        if (palindrome > 2)
            palindrome = 2;

        cout << palindrome << endl;
    }
}

하지만... 이 로직에는 치명적인 단점이 있었다.

 

왼쪽 포인터는 오른쪽 - 1의 값과 같은지, 오른쪽 포인터는 왼쪽 + 1과 같은지 검사할 때, 둘이 같은 경우는 처리해주지 않았던 것이다!

input =>
XYXYAAYXY

output =>
XYXYAAYX

answer =>
YXYAAYXY

그래서... 먼저 쓴 코드가 처리 된다는 점...

 

많은 고민을 하다가, 왼쪽이 오른쪽-1, 오른쪽이 왼쪽+1, 둘 중 하나라도 같은 게 확인이 된다면

둘 모두 팰린드롬인지 검사하고, 하나라도 팰린드롬이면 유사 회문 처리를 하고, 그렇지 않으면 회문이 아님을 처리한다.

 

#include<iostream>
using namespace std;

bool IsPalindrome(string str);
bool IsPseudoPalindrome(string str, int remove);

int main()
{
    int testCnt;
    cin >> testCnt;

    while (testCnt--)
    {
        string input;
        int answer = 0;
        cin >> input;

        for (int i = 0; i < input.size() / 2 + 1; i++)
        {
            int ri = input.size() - i - 1;

            // 값이 정해졌다면 break!
            if (answer > 0)break;
            if (input[i] == input[ri])continue;

            if (input[i] == input[ri - 1] || input[ri] == input[i + 1])
            {
                // 제거했을 때 둘 중 하나라도 팰린드롬이라면 유사팰린드롬
                // 그렇지 않으면 회문도, 유사회문도 아님
                if (IsPseudoPalindrome(input, ri) || IsPseudoPalindrome(input, i))
                {
                    answer = 1;
                }        
                else
                {
                    answer = 2;
                }
            }
            else
            {
                answer = 2;
            }
        }

        cout << answer << endl;
    }
}

// 팰린드롬 검사 함수
bool IsPalindrome(string str)
{
    for (int i = 0; i < str.size() / 2 + 1; i++)
    {
        int ri = str.size() - i - 1;

        if (str[i] != str[ri])
        {
            return false;
        }
    }

    return true;
}

// 유사 팰린드롬 검사 함수
bool IsPseudoPalindrome(string str, int remove)
{
    str.erase(str.begin() + remove);
    return (IsPalindrome(str));
}

확실히 시간이 조금 오래 걸리는 코드이지만, 깔끔한 것 같다.

 

코드에 조건을 걸 때도, 항상 여러 케이스를 생각하며 꼼꼼하게 조건을 달아야겠다!