백준 1254번 팰린드롬 만들기

문제 링크입니다: https://www.acmicpc.net/problem/1254

우선 이 문제를 푸는 방법은 두가지입니다.

둘다 팰린드롬 여부를 확인하는 코드이지만 Manacher 알고리즘 개념을 적용하면 보다 간결한 알고리즘 작성이 가능해집니다.

아래는 Manacher 알고리즘 개념을 알기 전에 작성한 코드입니다.

#include <iostream>

#include <string>

using namespace std;

 

string S;

int length;

 

int additionalLength(void)

{

        int result = 0;

 

        for (int i = 0; i < length - 1; i++)

        {

                 //양 끝이 같다면

                 if (S[i] == S[length - 1])

                 {

                         //하나씩 땡기면서 양 끝을 확인

                         int start = i;

                         int end = length - 1;

                         for (int j = 0; j < (length - i) / 2; j++)

                         {

                                 if (S[start] == S[end])

                                 {

                                          start++;

                                          end--;

                                 }

                                 else

                                 {

                                          result++;

                                          break;

                                 }

                         }

                         //더 이상 땡길 수 없을 경우

                         if (start >= end)

                                 break;

                 }

                 else

                         result++;

        }

        return result;

}

 

int main(void)

{

        cin >> S;

 

        length = S.size();

 

        cout << length + additionalLength() << endl;

        return 0;

}

Manacher 알고리즘은 알고스팟(https://algospot.com/wiki/read/Manacher's_algorithm)에 잘 설명되어있습니다.(갓종만)

아래는 Manacher 알고리즘 개념을 적용하여 푼 알고리즘입니다.

#include <iostream>

#include <string>

#include <cstring> //memset

using namespace std;

 

const int MAX = 1000;

 

string S;

int length;

 

bool palindrome(int idx)

{

        for (int i = 0; idx + i < length - i - 1; i++)

                 //하나라도 성립안하면 palindrome 아님

                 if (S[idx + i] != S[length - i - 1])

                         return false;

        return true;

}

 

int main(void)

{

        cin >> S;

 

        length = S.size();

        int result = 0;

 

        //1. 주어진 문자열의 길이 length일 때 palindrome 되는지 확인

        //2. 1번이 성립 안되면 length+1일 때 palindrome 되는지 확인

        //length - 2 까지 계속 확인 ...

        //length-1. length-2번이 성립 안되면 length+length-1일 때 palindrome

        for(int i=0; i<length; i++)

                 if (palindrome(i))

                 {

                         result = length + i;

                         break;

                 }

       

        cout << result << endl;

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~