[백준,c++] 1254번 - 팰린드롬 만들기

문제

1254번: 팰린드롬 만들기

 

코드

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


bool isPalindrom(string inp){
    string temp = inp;
    reverse(inp.begin(), inp.end());
    if(temp==inp) return true;
    return false;
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    string s; cin>>s;
    int ans = 1e9;
    string temp = s;
    reverse(temp.begin(),temp.end());
    if(s==temp){
        cout<<s.length();
        return 0;
    }
    
    for(int i=0; i<s.length(); i++){
        string temp = s.substr(i,s.length());
        if(isPalindrom(temp)){
            int len = s.length()-temp.length();
            ans = min(ans, len);
        }
    }
    if(ans==1e9) cout<<s.length()*2;
    cout<<ans+s.length();
}

 

풀이

문제 구현 방법은 아래와 같습니다.

1. 현재 문자가 펠린드롬이라면 현재 문자의 길이를 바로 출력합니다.
2. 현재 문자가 펠린드롬이 아니라면 현재 문자를 쪼갰을 때 존재하는 펠린드롬을 찾습니다.
3. 현재 문자에서 펠린드롬을 빼고 남은 문자를 뒤집어서 붙여주면 펠린드롬이 만들어집니다.

2번과 3번에 대해서 더 자세히 알아보겠습니다. 입출력 "acaa"가 있다고 가정해 보겠습니다. 현재 이 문자 안에서 존재하는 펠린드롬은 "aca"와 "aa"입니다.

• "aca"일 때는 "acaa"에서 "aca"를 제외한 "a"를 뒤집어서 붙여주면 "aacaa"로 펠린드롬이 완성됩니다. 
• "aa"일 때는 "acaa"에서 "aa"를 제외한 "ac"를 뒤집어서 붙여주면  "acaaca"로 펠린드롬이 완성됩니다.

문제에서는 가장 짧은 펠린드롬을 출력하라고 했기 때문에 "aacaa"의 길이인 5를 출력하면 됩니다.