백준 1254. 팰린드롬 만들기

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

1254번: 팰린드롬 만들기

 

 

이 문제는 처음에 주어진 문자열에 존재하는 알파벳들을 뒤에 일일히 붙여서 팰린드롬인지 판별하도록 짜다가

훨씬 좋은 방법이 있을것 같아서 찾아봤다.

 

먼저 팰린드롬이란 앞에서 읽으나 뒤에서 읽으나 같은 문자열이다.

그렇다면 팰린드롬이 아닌 주어진 문자열에서, 뒤에서부터 팰린드롬인 문자열을 찾으면 그 팰린드롬인 부분문자열을 제외한 나머지를 뒤에 붙이면 전체 문자열이 팰린드롬이 된다.

 

이렇게 말하니 햇갈리니 예를들자면 주어진 문자열이 abcc 라면 

앞에서부터 문자를 잘라본다:

abcc  // 팰린드롬이 아니다

bcc // 팰린드롬이 아니다  

cc   // 팰린드롬이다!

 

cc가 팰린드롬이므로 원래 문자열 abcc에 cc를 제외한 ab를 거꾸로 붙이면 abccba가 되고 팰린드롬이 된다.

그러나 문제에서는 길이만 구하면 되므로 실제로 뒤에 붙여볼 필요는 없고 크기만 계산하면 된다.

 

#include <iostream>
#include <string>

using namespace std;

string s;

// 팰린드롬인지 판별
bool IsItPalindrome(string str)
{
    int mid = str.size() / 2;

    for(int i = 0; i < mid; i++)
    {
        if(str[i] != str[str.size()-1-i])
            return false;
    }
    return true;
}

int main()
{
    cin >> s;

    // 문자열 s를 앞에서부터 잘라서 팰린드롬을 찾는다 
    for(int i = 0; i < s.size(); i++)
    {
        string temp = s.substr(i, s.size()-i);

        if(IsItPalindrome(temp))
        {
            cout <<  s.size() + i;
            return 0;
        }
    }
}