[프로그래머스 Level 3] 가장 긴 팰린드롬 (C++)

코딩테스트 연습 - 가장 긴 팰린드롬 | 프로그래머스 스쿨 (programmers.co.kr)

프로그래머스

 

 

처음 보는 알고리즘이어서 알고리즘 공부를 먼저 한 이후에 풀었다. 알고리즘에 대한 설명은 이전 블로그에 있다.

 

 

#include <iostream>
#include <string>
#include<algorithm>
using namespace std;
int dp[100000];

int solution(string s)
{
    int answer=1;
    string st="";
    for(int i = 0 ; i<s.size(); i++){
        st+="#";
        st+=s[i];
    }
    st+="#";
    
    int lastIdx = 0;
    int centerIdx = 0;

    for(int i = 1; i < st.size()-1; i++){
        if(lastIdx>=i){
            dp[i]=min(dp[2*centerIdx-i],lastIdx-i);
        }
        while (i-dp[i]-1>=0&&i+dp[i]+1<st.size()
               &&st[i-dp[i]-1]==st[i+dp[i]+1]) {
            dp[i]++;
        }
        if(dp[i]+i>lastIdx){
            lastIdx=dp[i]+i;
            centerIdx=i;
        }
    }
    return max(answer, *max_element(dp, dp+100000));
}