Gidhub BE Developer

[Programmers] 가장 긴 팰린드롬

2018-08-02
goodGid

Problem

Problem URL : 가장 긴 팰린드롬


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


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;
}



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

  • O(n)의 manachers 알고리즘

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


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


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;
}


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

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

Index