회문(팰린드롬)

팰린드롬이란?

팰린드롬은 문자열의 시작부터 끝부터 읽은 것과 끝에서 시작까지 읽은 것이 동일한 문자열이다

이거 알면 늙은거

이제 어떻게 문자열이 팰린드롬인지 판별할 수 있을까??

처음부터 끝까지, 끝부터 처음까지 읽어봐

가장 무식하고 쉬운 방법이다. 각각 O(n)의 시간 복잡도이기에 입력이 엄청 크지 않은 이상 통과할 수 있다

하지만 이번 챌린지 문제처럼 어떤 조건이 들어가는 경우는 조금 힘들다

bool IsPalindrome(string s)
{
    string s_reverse = s;
    reverse(s_reverse.begin(), s_reverse.end());

    for (int i = 0; i < s.size(); i++)
    {
        if (s[i] != s_reverse[i])
            return false;
    }
    
    return true;
}

int main()
{
    cout << IsPalindrome("abcba");
    cout << IsPalindrome("abcbad");
    return 0;
}

// 1
// 0

투 포인터(Two Pointer)

팰린드롬이 거꾸로 해도 똑같은 문자열이면 처음과 끝을 가리키는 왼쪽, 오른쪽 포인터를 두고 비교해가며 왼쪽 포인터를 증가시키고 오른쪽 포인터를 감소시키면서 왼쪽 포인터가 오른쪽 포인터보다 커질 때까지 팰린드롬을 검사할 수 있다

그럼 연산량도 반으로 줄 것이다. 그럼 시간 복잡도는 O(log N)이 될까??

그렇지 않다. 왜냐면 우리가 잘 아는 빅오 표기법은 상수배를 무시한다(여기까지 왔으면 아차 싶을 것)

그래서 연산량이 n/2로 줄어도 n이 어마어마하게 커지면 단일 포인터의 연산량인 N과 별 차이가 없을 것이라 시간 복잡도는 O(log N)이 된다

bool IsPalindrome(string s)
{
    int left = 0;
    int right = s.length() - 1;

    while (left < right)
    {
        // 왼쪽 포인터와 오른쪽 포인터가 같지 않다면 팰린드롬 탈락
        if(s[left] != s[right])
        {
            return false;
        }

        // 포인터 이동
        left++;
        right--;
    }

    // 무사히 반복문을 빠져 나오면 팰린드롬이 맞다
    return true;
}

재귀

재귀를 이용해서 팰린드롬을 확인할 수 있다. 문자열을 분할하며 부분의 답으로 전체의 답을 구한다

bool IsPalindrome(string s, int left, int right)
{
	// 모든 비교가 끝날 때까지 문제가 없다면 true 리턴
    if (left >= right) return true;
    if (s[left] != s[right]) return false;  // 같지 않는 문자열이 발생하면 false를 리턴

    return IsPalindrome(s, left + 1, right - 1);
}

스택

스택을 이용해서 문자열의 전반부를 스택에 담고 후반부와 비교한다. 만약 문자열이 홀수라면 중간 문자를 스택에 담지 않는다

bool IsPalindrome(string s)
{
    stack<int> stack;
    int len = s.length();

    for (int i = 0; i < len / 2; i++)
    {
        stack.push(s[i]);
    }

    int start = (len % 2 == 0) ? len / 2 : len / 2 + 1;

    for (int i = start; i < len; i++)
    {
        if (stack.top() != s[i])
            return false;
        stack.pop();
    }

    return true;
}

문제 풀어보기

백준 17609번 : 회문(골드 5)

이 문제는 어떤 문자열이 팰린드롬인지 확인하는데 문자열에서 한 문자만 제거하면 팰린드롬이 되는 유사 팰린드롬인지도 확인하는 문제이다

처음 풀이에서는 팰린드롬을 투 포인터로 검사하다가 같지 않는 부분이 나오면 왼쪽 포인터 + 1 == 오른쪽 포인터라면 왼쪽 포인터를 증가시키고 왼쪽 포인터 == 오른쪽 포인터 - 1이라면 오른쪽 포인터를 감소시켰다

그리고 한번만 제거할 수 있으니 부울 변수로 기록해 다음에도 또 같지 않으면 그때 팰린드롬 수가 아니라고 판별하도록 했다

근데 일단 틀렸다. 여러 경우의 수를 파악하지 못했다. 왼쪽 포인터를 1 증가시킨 경우와 오른쪽 포인터를 1 감소시킨 경우 모두를 생각해야 했다

그래서 다시 생각한 방법은 처음에 팰린드롬 검사를 하다가 왼쪽과 오른쪽이 같지 않을 때 왼쪽 + 1의 경우와 오른쪽 -1의 경우를 함수 호출을 다시해서 그 문자열이 팰린드롬이면 부분 팰린드롬이고 팰린드롬이 아니면 팰린드롬이 아니다

코드

#include <bits/stdc++.h>

using namespace std;

int T;

bool IsPalindrome(string s, int left, int right)
{
    while (left < right)
    {
        if (s[left] == s[right])
        {
            left++;
            right--;
        }
        else
        {
            return false;
        }
    }

    return true;
}

int main()
{
    cin >> T;

    while (T--)
    {
        string s;
        cin >> s;

        int left = 0;
        int right = s.length() - 1;
        int result = 0;

        while (left < right)
        {
            if (s[left] == s[right])
            {
                left++;
                right--;
            }
            else
            {
                if (IsPalindrome(s, left + 1, right) || IsPalindrome(s, left, right - 1))
                {
                    result = 1;
                    break;
                }
                else
                {
                    result = 2;
                    break;
                }
            }
        }
        cout << result << '\n';
    }

    return 0;
}