백준 17609 회문 (c++) : 피너클

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

17609번: 회문

 

회문을 찾는 함수를 먼저 만든다.

앞뒤 문자가 같으면 true를 반환하고 앞뒤 문자가 다르다면 false를 반환하게 한다.

문자열을 string str로 입력받고 맨 처음은 int s로 맨 마지막을 int e로 잡는다.

처음의 int s의 값은 0이 되고 int e의 값은 (문자열의 길이 - 1)가 된다.

str[s]의 문자와 str[e]의 문자가 같으면 s는 1을 추가하고 e는 1을 뺸다.

이번에도 str[s]의 문자와 str[e]의 문자가 같으니 s에 1을 추가하고 e에 1은 뺸다.

만약 s와 e의 값이 같아진다면 같은 자리에 있다는 뜻이니 무조건 문자의 값이 같아지고 

s가 e보다 크다면 모든 값을 둘러봤다는 뜻이니 true를 반환하면 된다.

한번이라도 str[s]값과 str[e]값이 다르면 false를 반환한다.

 

유사회문은 어떻게 구현해야 할까

일반적인 회문과 비슷하다. int s와 int e를 두고 str[s]값과 str[e]를 확인한다.

만약 str[s]값과 str[e]값이 다르다면 둘중 한가지 값을 제거해야한다.

간단하다 s+1값과 e값을 비교하면된다. 이렇게 되면 str[s]값을 제거한 효과를 얻을수 있다.

또한 str[s]값과 str[e-1]값을 비교할수도 있다. 이 둘중 하나라도 회문이 된다면 유사회문이라는 뜻이다.

위의 과정을 제외하면 회문과 같다.

하지만 위의 과정을 오직 한번만 수행해야하기 때문에 bool값을 써서 수행했나 안했나를 확인해도 되고

int값을 써서 int가 1이면 수행하고 int가 0이면 수행안하고 이런식으로 코드를 짜면 된다.

팰린드롬을 체크하고 팬린드롬이면 0을 출력

팰린드롬이 아니면 유사팰린드롬을 체크, 유사팰린드롬이면 1을 출력

둘다 아닐경우에는 2를 출력하면 된다.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
 
string str;
 
bool pallndrome(int s, int e) {
    if (s == e || s > e)
        return true;
    if (str[s] != str[e])
        return false;
    else
        return pallndrome(s + 1, e - 1);
}
int check;
bool pseudoPallndrome(int s, int e) {
    if (s == e || s > e)
        return true;
    if (str[s] != str[e]) {
        if (check == 1) {
            check = 0;
            if (pseudoPallndrome(s + 1, e) || pseudoPallndrome(s, e - 1))
                return true;
            else
                return false;
        }
        else
            return false;
    }
    else
        return pseudoPallndrome(s + 1, e - 1);
}
 
int main()
{
    int t;
    cin >> t;
    while (t-- > 0) {
        check = 1;
        cin >> str;
        if (pallndrome(0, str.length()-1)) {
            cout << 0 << endl;
        }
        else if (pseudoPallndrome(0, str.length()-1)) {
            cout << 1 << endl;
        }
        else
            cout << 2 << endl;
 
    }
}