[백준/Baekjoon] 1254 팰린드롬 만들기 C++ :: String

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

1254번: 팰린드롬 만들기

 

---

1. Logic

- 주어지는 문자열의 갯수가 최대 50이니 시간복잡도를 계산해 봤을때

각 자리수에서 1씩 증가하며 뒤에 붙히고 팰린드롬을 확인하는 최악의 경우의 수를 생각해도 50 * 50 * 50 정도일 것이라고 생각해서 2초안에 충분히 돌 수 있다고 판단함. > 전부 확인해 보기

 

- str[0]부터 1씩 증가해가며 str의 뒤에 붙히고 팰린드롬인지 확인하기

 

2. Code

#include<bits/stdc++.h>

using namespace std;

bool isPali(string str) {
    string temp = str;
    reverse(temp.begin(), temp.end());

    if(temp == str) return true;
    else return false;
}

int main() {
    string str, ans;
    cin >> str;

    if(isPali(str)) {
        cout << str.size();
        return 0;
    }

    for(int i = 0; i < str.size(); i++) {
        string temp = str;
        for(int j = i; j >= 0; j--) {
            temp += str[j];
            if(isPali(temp)) {
                cout << temp.length();
                return 0;
            }
            else continue;
        }
    }
}