백준 1254번. 팰린드롬 만들기(c++) / 문자열

모기업 코드페스티벌에 참여했는데,,,, 유일하게 풀지 못했던 문제;;;; ㅂㄷㅂㄷ

팰린드롬인지 아닌지를 판별하는 문제는 쉽게 풀었었는데

만드는 문제는 처음 접해서 당황했다.... 끝나고 백준을 찾아보니 역시나 똑같은 문제가 있었다 ㅋㅋㅋ

그래서 다른 분의 코드를 참조해서 다시 풀어보았다!

 

[메인 로직]

해결방법은 인덱스가 0인 지점부터 차례대로 조사하며 팰린드롬이 되는 최소한의 시작 위치를 찾는 것이다.

어차피 중간에 팰린드롬이 생기는 것은 아무 의미가 없기 때문에특정 인덱스부터 문자열의 맨 마지막까지 팰린드롬이 되는 부분 문자열을 찾으면, (특정인덱스+원래 문자열의 크기)가 최소 팰린드롬의 길이가 되는 것이다.

aabcaa인 경우에는 맨 뒤의 aa만 팰린드롬이 가능하다 따라서 aa는 그대로 두고 나머지 aabc만 뒤집어서 추가해주면 가장 짧은 팰린드롬 문자열이 생성된다. => 길이는 4+6 = 10

aabcba를 생각해보자. 맨 앞의 a를 제외하고 나머지 abcba가 팰린드롬이므로 마지막에 a만 추가해주면 팰린드롬이 성립한다. => 길이는 1+6 = 7

 

// 팰린드롬 만들기
#include <iostream>
using namespace std;
 
string s;
int answer = 0;
 
bool isPalindrom(string str)
{
    int cnt = str.size()/2;
    for(int i=0; i<cnt; i++){
        if(str[i]!=str[str.size()-1-i]){
            return false;
        }
    }
 
    return true;
}
 
int main()
{
    cin>>s;
 
    answer = s.size()*2-1;
    for(int i=0; i<s.size(); i++){
        string temp = s.substr(i, s.size()-i);
        if(isPalindrom(temp)){
            answer = s.size()+i;
            break;
        }
    }
 
    cout<<answer<<"\n";
    return 0;
}