Programmers - 가장 긴 팰린드롬

---

title: Programmers - 가장 긴 팰린드롬
date: 2022-08-14
tags:

• Algorithm
• DP

---

https://school.programmers.co.kr/learn/courses/30/lessons/12904

문제 요약

문자열을 뒤집어도 동일하다면 이를 Palindrome이라고 한다.
주어진 문자열의 substring 중 가장 긴 Palindrome의 길이를 return한다.

문제 풀이

이 문제는 알고리즘 설계를 잘 했다면 쉬운 문제이고, 설계 없이 부딪혔다면 어려운 문제일 것이다.
모든 substring을 확인해야하며, 이를 전부 꺼내어 확인하기에는 매우 비효율적이다.
간단한 예시를 보이면 알고리즘을 떠올리기 쉽다.
QabWbaE 라는 문자열이 존재한다. Q, W, E 는 문자가 아닌 문자열이지만 대충 적은 것이므로 이 부분은 건너뛰고, abWba를 보자.
우선 양 끝이 같은 문자이므로, 두 문자를 제외한 내부가 Palindrome이면 이것 또한 Palindrome이다.
끝을 제외한 bWb의 경우, 동일하게 양 끝이 같으므로 내부를 확인한다.
남은 W 부분이 Palindrome인지 확인하면 되는 것이다.
결국 이 문제는 같은 문자가 발견될 경우, 그 두 문자를 제외한 사이에 존재하는 문자열에 대해 Palindrome인지 확인하면 되는 문제이다.
이를 매 처리마다 substr 혹은 재귀 처리를 한다면 TLE가 나올 것이다. 그렇게 풀면 틀리도록 문제를 만들었을 것이다.
그러므로 사이에 있는 문자열에 대해서는 이미 Palindrome 처리가 끝나있어야 한다. 그러므로 이 문제는 DP 문제이다.


2차원 vector를 이용한다. [ Start Index ] [ String Size ]에는 Start Index부터 String Size까지 Palindrome이라면 그 길이가 들어갈 것이다.
우선 모든 값은 0으로 초기화한다. Palindrome이 아닐 경우 이미 값이 0이므로 추가 처리를 할 필요가 없다.
문자열의 첫 문자부터 하나씩 동일한 처리를 반복해주면 된다.
n번째 문자를 검사한다. 한 글자만 존재하면 그 자체로 Palindrome 이므로 [ n ] [ 1 ] = 1 처리를 해준다.
이후 0 ... n-1 각 문자에서 n번째 문자까지 Palindrome인지 확인해주면 n번째까지의 모든 substring에 대한 Palindrome 검사가 완료된 것이다.
각 시작 문자와 n번째 문자가 같은지, 그리고 같다면 그 사이의 문자열이 Palindrome인지 확인한다. Palindrome이라면 시작 문자부터 n번째 문자까지의 길이를 저장한다.
여기서 Palindrome 검사를 할 때 값이 0인지 비교하는데, n-1번째 문자부터 n번째까지 비교하면 사이의 문자열은 0이므로 무조건 Palindrome이 아니라고 할 것이다.
그렇기에 이런 2개짜리 문자열은 추가 처리를 해주어야 한다.


정확성 테스트 결과 최대 약 0.05ms, 효율성 테스트 결과 최대 약 40.8ms의 좋은 성능을 확인할 수 있다.

프로그램

#include <string>
#include <vector>
#include <algorithm>

using std :: string ;
using std :: vector ;
using std :: max ;

int solution ( string s )
{
    int answer = 1 ;
    int iStringSize = s.size () ;
    vector < vector < int > > vDP ( iStringSize , ( vector < int > ( iStringSize + 1 , 0 ) ) ) ;        // [ Start Index ] [ Length ]
    const char * cpString = s.data () ;



    vDP [ 0 ] [ 1 ] = 1 ;
    for ( int i = 1 ; i < iStringSize ; ++i )
    {
        char cCurrent = cpString [ i ] ;
        vDP [ i ] [ 1 ] = 1 ;

        for ( int iIndex = 0 ; iIndex < i ; ++ iIndex )
        {
            if ( ( cCurrent == cpString [ iIndex ] ) && ( 0 != vDP [ iIndex + 1 ] [ i - iIndex - 1 ] ) )
                vDP [ iIndex ] [ i - iIndex + 1 ] = cCurrent == cpString [ iIndex ] ? vDP [ iIndex + 1 ] [ i - iIndex - 1 ] + 2 : 0 ;
            vDP [ iIndex ] [ 2 ] = cCurrent == cpString [ iIndex ] ? 2 : 0 ;

            answer = max ( answer , vDP [ iIndex ] [ i - iIndex + 1 ] ) ;
        }
    }


    return answer ;
}