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

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

 

회문이란?

좌우대칭인 문자열을 의미한다. 

ABA

ABBA 같은 문자열이 회문이다.

 

해당 문제는 문자 하나까지는 봐줄 때 회문인지를 판단할 수 있는지를 물어보는 문제이다.

 

풀이방향

1. 회문인지 파악하는 방법

• 문자열의 시작과 끝에서 서로 비교하면서 틀린것이 없다면 회문 (시간복잡도 N) 

2. 하나 생략을 하는 방법

• 1번 로직을 진행하다가 하나만 더 진행시키면 된다. 예를들어 ABCBDA 를 하고 있었다면 B(1)와 D(5)가 다를 때, 왼족 인덱스만 1 증가 시키거나 오른쪽 인덱스만 하나 감소 시키면 된다.

3. 그렇다면 이것은 같은 방식을 계속 다시 써야할 것 같다.

• 회문파악을 계속하면서 두 값이 다를 때만 인덱스를 변화시키므로 재귀를 돌면 될 것 같다. 

 

슈도코드

1. left, right 인덱스로 문자 비교

2. 같으면 left + 1, right - 1 시켜서 비교반복

3. 다른데 이미 생략을 썼으면 return false, 아직 기회 있으면 left + 1만 / right -1 만 시켜서 반복

4. left == right (문자열길이 홀수) or left > right (문자열길이짝수) 이면 true

 

정답코드

#include <iostream>
#include <deque>
using namespace std;
string s;
pair<bool, bool> recusion(int left, int right, bool flag) {
    if(left == right || left > right) {
        return {true, flag};
    }

    if(s[left] == s[right]) {
        left++;
        right--;
    
        return recusion(left, right, flag);
    } else {
        if(!flag) {
            return {false, false};
        } else {
            pair<bool, bool> frontpop = recusion(left + 1, right,false);
            pair<bool, bool> backpop = recusion(left, right - 1, false);

            return { frontpop.first || backpop.first, false };
        }
    }
}

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

    for(int i = 0; i < N; i++) {
        cin >> s;

        pair<bool, bool> res = recusion(0, s.size() - 1, true);

        if(res.first) {
            if(res.second) {
                cout << 0 << "\n";
            } else {
                cout << 1 << "\n";
            }
        } else {
            cout << 2 << "\n";
        }
    }
}