[백준] #17609 회문

17609번: 회문 (acmicpc.net)

17609번: 회문

#1254에서 다뤘던 팰린드롬 관련 문제이기도 했고, 애초에 그리 어려운 문제는 아니었지만, 중간에 반례를 찾던중 접근 방식을 한번 갈아 엎어서 시간이 오래 걸렸다.

---

팰린드롬 (palindrome) / 회문 (回文)
앞에서부터 읽으나 뒤에서부터 읽으나 같게 읽히는 문자열을 말한다.

#1254 팰린드롬 만들기와 같은 내용을 담고있어서 접근하기엔 수월했다.

---

처음엔 #1254에서의 코드를 조금 고쳐 함수 하나로 처리하도록 만들었다.

• 기존 C++ 코드 (함수만)

int F(string s) {
    int len = s.length();
    string::iterator front = s.begin(), back = --s.end();
    bool flag = true;

    int t;
    len%2 == 0 ? t = len/2 : t = len/2 + 1;

    while (t-- > 0) {
        if (*front != *back) {
            if (*(front+1) == *back && flag) {
                flag = false;
                front++;
                continue;
            }
            else if (*front == *(back-1) && flag) {
                flag = false;
                back--;
                continue;
            }
            else if (!flag) return 2;
        }
        front++;
        back--;
    }
    if (flag) return 0;
    
    return 1;
}

그런데, 이 함수를 이용하여 구하면 abcddcdba라는 반례가 존재하게 된다.

이는 분명 문자 d 하나만 없으면 회문이 되는 유사회문이어서 1이 출력되어야 하는데, 결과값은 2가 나오게 된다.

따라서, 저 함수를 기본 베이스로 회문을 판별하는 isF / 왼쪽과 오른쪽을 나누어 유사회문을 판별하는 isLF, isRF로 함수를 쪼개어 최종적으로 구현하였다.

또한, string의 index에 바로 접근하지 않고, string::iterator 즉 포인터로 접근하여 구현하였다.

---

• 최종 C++ 코드

#include <iostream>
#include <string>

using namespace std;

bool isF(string s) {
    string::iterator front = s.begin(), back = --s.end();
    int len = s.length(), t;

    len%2 == 0 ? t = len/2 : t = len/2 + 1;

    while (t-- > 0) {
        if (*front != *back) return false;

        front++;
        back--;
    }
    return true;
}
bool isLF(string s) {
    string::iterator front = s.begin(), back = --s.end();
    int len = s.length(), cnt = 0;

    while (front <= back) {
        if (*front != *back) {
            cnt++;
            front++;
            continue;
        }
        if (cnt > 1) return false;

        front++;
        back--;
    }
    return true;
}
bool isRF(string s) {
    string::iterator front = s.begin(), back = --s.end();
    int len = s.length(), cnt = 0;

    while (front <= back) {
        if (*front != *back) {
            cnt++;
            back--;
            continue;
        }
        if (cnt > 1) return false;

        front++;
        back--;
    }
    return true;
}

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

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

        if (isF(s)) cout << 0 << '\n';
        else if (isLF(s) || isRF(s)) cout << 1 << '\n';
        else cout << 2 << '\n';
    }

    return 0;
}