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

백준의 회문(17609) 문제이다.

[ 문제 바로가기 ]

 

[ 문제풀이 ]

주어진 문자열이, 회문인지, 유사회문인지, 둘 다 아닌지를 판단해서 출력해야 하는 문제이다.

 

#1. 접근방법

먼저, 본인은 이 문제를 재귀를 이용해서 접근해 보았다.

2개의 포인터인 Left와 Right를 이용해서 이를 매개변수 삼아서 재귀를 진행해주었다.

Left는 주어진 문자열에서 0번 Index부터 증가하는 포인터를 나타내는 변수이고 , Right는 주어진 문자열에서 마지막 Index부터 감소하는 포인터를 나타내는 변수이다.

회문이라면, 주어진 문자열의 Left값과 Right 값이 같아야 하기 때문이다.

예를 하나 들어보자.

"abba" 라는 문자열이 있다. 가장 초기에, Left의 값은 0, Right의 값은 3이 될 것이다.

string[0] = string[3] 은 'a'로 똑같은 문자이기 때문에 여기까지만 본다면 이 문자열은 회문이다.

이후에, Left값이 증가하고, Right값이 감소해서 string[1]과 string[2]를 비교하면 'b'로 똑같은 문자이기 때문에 결과적으로 이 문자열은 회문이 되는 것이다.

이런식으로, Left Index와 Right Index가 가지는 문자들을 비교하기 위해서 Left와 Right를 매개변수로 호출해 주었다.

 

#2. 회문이 아닌 경우

그런데 이 문제에서는 회문이 아닌 경우도 2가지로 나뉘게 된다. 바로, 유사회문인지 아니면 유사회문도 아닌지를 판단해 주어야 한다.

유사회문은 한 개를 삭제를 해서 회문이 되는 경우이다.

그렇다면, 한개를 삭제 해야 한다면, 어느 순간 Left Index가 가지는 값과 Right Index가 가지는 값이 다르다는 것을 의미한다.

만약 같다면, 삭제를 할 이유가 없을 것이다. 삭제를 해야 한다면, 위의 2개의 값이 다르다는 것을 의미한다.

그렇다면 ! 달랐을 때 체크를 해줘야 되는 것이 또 하나 있다.

바로, "지금까지 삭제한 횟수가 0회인지 ?"를 판단해 주어야 한다. 이미 기존에 1번 삭제를 해버렸는데 또 삭제를 필요로 하는 상황이 나왔다면 이는 유사회문도 안되기 때문이다.

 

만약, 삭제한 횟수가 0회라면 여기서는 2가지 경우가 발생할 수 있다.

Left의 값을 삭제하거나, Right의 값을 삭제하거나 !

Left와 Right의 값이 다르다면, 어느 하나는 삭제를 해야 할텐데 그 어느 하나를 삭제할지에 대해서도 계산을 해줘야 하는 것이다.

그래서, 어느 하나를 삭제를 했을 때, 그 결과가 회문이라면 이는 유사회문이 되는 것이다.

그런데, 이 결과가 유사회문이 아니라면 결국 이 문자열은 회문도, 유사회문도 아니라는 것을 의미한다.

 

[ 소스코드 ]

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
int T;
vector<string> V;
 
void Input()
{
    cin >> T;
    for(int i = 0 ; i < T; i++) 
    {
        string S; cin >> S;
        V.push_back(S);
    }
}
 
int Is_Palindrome(int Left, int Right, int Delete, string Str)
{
    while(Left < Right)
    {
        if(Str[Left] != Str[Right])
        {
            if(Delete == 0)
            {
                if(Is_Palindrome(Left + 1, Right, 1, Str) == 0 || Is_Palindrome(Left, Right - 1, 1, Str) == 0) return 1;
                return 2;
            }
            else return 2;
        }
        else 
        {
            Left++;
            Right--;
        }
    }
    return 0;
}
 
void Solution()
{
    for(int t = 0 ; t < T; t++)
    {
        string Str = V[t];
        int Result = Is_Palindrome(0, Str.length() - 1, 0, Str);
        cout << Result << endl;
    }
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    Solve();
}