[BOJ/C++] 17609: 회문

🏅 Gold 5

✏️ 1차 솔루션

완전탐색으로 풀이한 것이나 다름없음
1. 문자를 반으로 나누고 길이가 홀수이면 가운데 문자를 두 개의 문자 끝에 붙이기
2. 회문 검사
1) 앞쪽 문자랑 뒤쪽 문자가 같으면 회문
2) 같지 않으면 하나 뺄 문자 찾아야하기 때문에 한 쪽 문자의 현재 인덱스 문자와 다른 쪽 문자의 다음 인덱스가 같으면 한 문자 뺄 수 있는 것이기 때문에 다른 쪽 문자의 현재 인덱스 자리를 지워주기
3) 한 번 지워도 탐색이 끝나지 않으면 회문이 아닌 것으로 판별

🚨 trouble

그냥 틀려버림..
이 방법으로도 해결해볼 수 있을 것 같지만 복잡하고 그리 좋은 방법은 아닌 것 같음

✏️ 최종 솔루션

⭐️ 투 포인터

1. 현재 두 포인터의 문자가 같으면 포인터를 점점 중앙쪽으로 옮기면서 계속 같은지 확인
   ❗️ 현재 문자를 뺀 개수는 계속 count 해줘야 함
2. 두 포인터의 문자가 같지 않을 경우
   1) 이미 문자를 뺐다면 회문이 될 수 없다고 판단
   2) 문자를 뺀 적이 없다면 오른쪽 포인터만 옮겼을 경우와 왼쪽 포인터만 옮겼을 경우를 재귀해서 두 개의 루트중에 회문이라면 1 return

📌 self feedback

한 문자 체크할 때마다 재귀해서 하는 방법은 메모리 초과 문제가 발생할 수 있기 때문에 문자가 맞지 않을 때마다 재귀를 돌려서 왼쪽 포인터를 오른쪽으로 옮기는 경우와 오른쪽 포인터를 왼쪽으로 옮기는 경우 모두에 대해 회문인지 검사하면 효율적으로 풀이할 수 있음
아예 cnt 를 0,1,2 만 존재할 수 있도록 사전 세팅하는 과정이 필요했음
문자열 문제 풀이할 때 속도도 줄이고 int 형 재귀함수에도 익숙해질 필요가 있음

✏️ 최종 code

#include <iostream>
#include <string>
using namespace std;

int dfs(string s, int l, int r, int cnt) {

    while(l<r) {
        if(s[l]!=s[r]) {
            if(cnt==0) {
                if(dfs(s,l+1,r,1)==0 || dfs(s,l,r-1,1)==0 ) return 1;
                return 2;
            }
            else return 2;
        }
        else {
            l++;
            r--;
        }

    }
    return 0;

}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int t;
    cin >> t;

    while(t--) {
        string s;
        cin >> s;

        cout << dfs(s,0,s.size()-1,0) << endl;
    }

}