---
layout: post
title:  " Programmers - 가장 긴 팰린드롬 "
excerpt: " 가장 긴 팰린드롬 "
date:   2018-08-02
cate : "algorithm"
tag:
- Programmers
---

## Problem 
Problem URL : **[가장 긴 팰린드롬](https://programmers.co.kr/learn/courses/30/lessons/12904)**

---

## [1] Answer Code (18. 08. 02)

{% highlight cpp %}

const int MAXN = 100001 * 2;
int A[MAXN];

string str;

void manachers(string S, int N){
    int r = 0, p = 0;
    for (int i = 0; i < N; i++){
        if (i <= r)
            A[i] = min(A[2 * p - i], r - i);
        else
            A[i] = 0;
        
        while (i - A[i] - 1 >= 0 && i + A[i] + 1 < N && S[i - A[i] - 1] == S[i + A[i] + 1])
            A[i]++;
        
        if (r < i + A[i]){
            r = i + A[i];
            p = i;
        }
    }
}

int solution(string s){
    int len = (int)s.size();
    
    for (int i = 0; i < len; i++)
    {
        str += '#';
        str += s[i];
    }
    str += '#';
    
    manachers(str, (int)str.size());
    
    len = (int)str.size();
    int ans = -1;
    for (int i = 0; i < len; i++)
        ans = max(ans, A[i]);
    
    return ans;
}


{% endhighlight %}

---

### [1] Answer Code (18. 08. 02)

* O(n)의 manachers 알고리즘

* 근데 알고리즘 이해가 안되서 그냥 사용...

---

## [1] Wrong Code (18. 08. 02)

{% highlight cpp %}

bool palindrome(int l, int r, string s){
    while (l < r) {
        if( s[l] == s[r] ){
            l++;
            r--;
        }
        else
            return false;
    }
    return true;
}

int solution(string s){
    int answer=0;
    int size = (int)s.length();
    
    for(int i=0; i<size; i++){
        for(int j=size-1; j>=i; j--){
            if( palindrome(i, j, s) ) {
                answer = answer < j-i+1 ? j-i+1 : answer;
                break;
            }
        }
    }
    return answer;
}



{% endhighlight %}

---

### [1] Wrong Code (18. 08. 02)

* TC는 모두 맞는데 시간초과 ... O(n^2)




Write PGM Post ' 가장 긴 팰린드롬 '
Write PGM Post ' 가장 긴 팰린드롬 '
