백준, BOJ, 17609번, 회문 C++ [CPP] ★★★

팰린드롬 문제이다.

나 엄청헤맸다.

ㅠㅠ

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

 

---

 

#맞은 풀이

#include <bits/stdc++.h>

using namespace std;
int T;

//좌측과 우측의 값을 순차적으로 비교
bool palindrome(string s) {
    //cout << s << '\n';
    int length = s.size();
    for (int i = 0; i < length / 2; i++)
        if (s[i] != s[length - i - 1])
            return false;
    return true;
}

bool subpalindrome(string s){
    int left = 0;
    int right = s.size()-1;
    while(left < right){
        if(s[left] != s[right])return false;
        left++;
        right--;
    }
    return true;
}



int check(string s){
   
    //회문
    if(subpalindrome(s))return 0;
    
    //유사회문
    int left = 0;
    int right = s.size()-1;
    
    while(left < right){
        if(s[left] != s[right]){
            //왼쪽 값을 삭제
            if(palindrome(s.substr(0,left) + s.substr(left+1)))return 1;
            //오른쪽 값을 삭제
            if(palindrome(s.substr(0,right) + s.substr(right+1)))return 1;
            
            return 2;
        }
        left++;
        right--;
    }

    return 2;
}
int main(){
    cin >> T;
    cin.tie(0);
    ios::sync_with_stdio(0);
    while(T--){
        string s;
        cin >> s;
        int x = check(s);
        
        
        
        
        cout << x<<'\n';
    }
    return 0;
}

 

팰린드롬을 검사하는 방법 2가지를 만들었다.

같은 방식이긴 하다만

여기서는 left, right로 검사하는 것이 더 좋았다.

index를 이용해야 했기 때문이다.

그리고 항상 느끼는 건데..? 문자열은 시간복잡도 금방 깨진다..ㅠ