백준 17609 - 회문

문제 설명

회문(回文) 또는 팰린드롬(palindrome)은 앞 뒤 방향으로 볼 때 같은 순서의 문자로 구성된 문자열을 말한다. 예를 들어 ‘abba’ ‘kayak’, ‘reviver’, ‘madam’은 모두 회문이다. 만일 그 자체는 회문이 아니지만 한 문자를 삭제하여 회문으로 만들 수 있는 문자열이라면 우리는 이런 문자열을 “유사회문”(pseudo palindrome)이라고 부른다. 예를 들어 ‘summuus’는 5번째나 혹은 6번째 문자 ‘u’를 제거하여 ‘summus’인 회문이 되므로 유사회문이다.

여러분은 제시된 문자열을 분석하여 그것이 그 자체로 회문인지, 또는 한 문자를 삭제하면 회문이 되는 “유사회문”인지, 아니면 회문이나 유사회문도 아닌 일반 문자열인지를 판단해야 한다. 만일 문자열 그 자체로 회문이면 0, 유사회문이면 1, 그 외는 2를 출력해야 한다. 

https://www.acmicpc.net/problem/17609

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, 문자열이 주어졌을 때 회문인지 확인하는 문제이다.

단, 유사회문이라는 것이 존재하는데 유사회문이란 문자열에서 단 하나의 문자를 빼 회문으로 만들 수 있는 문자열이다.

 

우선, 회문을 검사하는 방법은 간단하다.

앞에서부터 i번째 문자와 length-i번째 문자가 같은지 확인하면 된다.

하지만, 유사회문이라는 개념 때문에 해당 문제는 조금 까다롭다.

 

이를 해결하는 방법은 투포인터를 통해 회문을 검사하며 조작이 필요한 순간이 되면 문자열을 조작하는 것이다.

즉, i번째 문자와 length-i번째 문자가 다르다면 i번째 문자 혹은 length-i번째 문자를 뺀 후 진행한다.

하지만, 유사회문은 단 하나의 문자만 조작해야 하기 때문에 두 번째 조작부터는 더 이상 진행하지 않아도 된다.

 

예를 들어,

summuus

라는 문자열이 입력으로 주어졌다고 가정해 보자.

그렇다면, su까지는 회문이 된다.

2번 인덱스부터 다른 문자가 나타난다.

이때, left를 오른쪽으로 옮겨보거나 right를 왼쪽으로 옮기는 식으로 문자열을 조작할 수 있다.

단, 옮긴 인덱스의 문자가 나머지 하나의 문자와 같을 때만 이동해야 한다.

left를 오른쪽으로 옮긴다면 'm'과 'u'를 비교하게 되고 둘은 다른 문자이기 때문에 유사회문이 되지 않는다.

하지만, right를 왼쪽으로 옮긴다면 'm'과 'm'을 비교하게 되며 둘은 같은 문자이므로 유사회문이 될 수 있다.

 

이렇게 진행하면 대부분의 경우는 맞을 수 있지만 예외가 발생하는 부분이 존재한다.

left를 오른쪽으로 옮긴 결과와 right를 왼쪽으로 옮긴 결과 모두 유사회문이 될 수 있다면 무엇을 먼저 하는지에 따라 결과가 달라진다.

위와 같은 경우 left를 옮겨도 'x'와 'x'를 비교하고 right를 옮겨도 'b'와 'b'를 비교하게 된다.

하지만, 두 경우를 더 진행하게 된다면 다른 결과를 반환한다.

left를 옮기면 회문이 되지 않지만, right를 옮기면 회문이 된다.

이러한 경우에는 양쪽 모두 진행한 후 반환하는 값이 더 낮은 것을 택하면 된다.

회문의 경우 0, 유사회문은 1, 둘 다 아닌 경우 2를 반환하기 때문에 논리적으로 모순이 없다.

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

int N;
string str;

int IsPalindrome(int left, int right, int result)
{
    if (left >= right || result == 2) return result;

    if (str[left] == str[right])
    {
        result = IsPalindrome(left + 1, right - 1, result);
    }
    else if (str[left + 1] == str[right] && str[left] == str[right - 1])
    {
        result = min(IsPalindrome(left + 1, right, result + 1), IsPalindrome(left, right - 1, result + 1));
    }
    else if (str[left + 1] == str[right])
    {
        result = IsPalindrome(left + 1, right, result + 1);
    }
    else if (str[left] == str[right - 1])
    {
        result = IsPalindrome(left, right - 1, result + 1);
    }
    else
    {
        result = 2;
    }

    return result;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N;

    while (N--)
    {
        cin >> str;
        int result = IsPalindrome(0, str.length() - 1, 0);
        cout << result << "\n";
    }

    return 0;
}

---