프로그래머스 - 가장 긴 팰린드롬 (Lv.3)

문제 설명

• 길이가 n(2500이하)인 문자열이 주어질 때, 부분문자열 중에서 가장 긴 팰린드롬의 길이를 구하라

구현 (TC 2개 Fails, 효율성 테스트 시간초과)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

// 부분문자열이 펠린드롬인지 확인한다.
bool check_palindrome(string& org_str, int n, int front, int back){
    for(int i=0; i<n/2; i++){
        if(org_str[front+i] != org_str[back-i])
            return false;
    }
    return true;
}

// 문자열 파싱의 시작점, 끝점을 인자로 받아서 부분문자열을 만든다.
int get_len_substr_palindrome(string& org_str, int start, int end){
    int n = end - start + 1;

    if(check_palindrome(org_str, n, start, end))
        return n;
    else
        return 0;
}

int solution(string s)
{
    int answer=0;
    int n = s.length();
    
    for(int i=0; i<n-1; i++){
        for(int j=n-1; j>=i+1; j--){
            answer = max(answer, get_len_substr_palindrome(s, i, j));
        }
    }
    
    return answer;
}

개선한 점

• 모든 경우의 수에 대해서 탐색할 필요가 없다. 길이가 n인 부분문자열 중에서 펠린드롬을 찾아가고, 펠린드롬을 찾을 수 없는 경우 길이를 줄여간다.
• 투포인터를 통해 시간복잡도를 최대한 줄였다. 부분문자열의 맨 앞과 맨 뒤를 가리키는 front, back 변수를 두어 palindrome을 확인하였다.
• 부분문자열의 길이가 줄어들수록 front, back을 결정할 수 있는 경우의 수는 늘어나는데, 이에 대한 주의가 필요하다.

구현 (All pass)

#include <iostream>
#include <string>
#include <algorithm>
using namespace std;

bool check_palindrome(string& str, int len, int start, int end){
    for(int i=0; i<len/2; i++){
        if(str[start+i] != str[end-i])
            return false;
    }
    return true;
}

bool get_longest_palindrome(string& str, int substr_len){
    int orgstr_len = str.length();
    int diff = orgstr_len - substr_len;
    
    int start = 0, end = orgstr_len-1;
    int front, back;
    for(int i=0; i<=diff; i++){
        front = start + i;
        back = end - (diff-i);
        if(check_palindrome(str, substr_len, front, back))
            return true;
    }
    return false;
}

// 모든 경우의 수를 탐색하는 것이 아니라 길이가 최대인 팰린드롬부터 찾는다.
int solution(string s)
{
    int answer=0;
    int n = s.length();
    
    for(int substr_len=n; substr_len>0; substr_len--){
        if(get_longest_palindrome(s, substr_len)) {
            answer = substr_len;
            return answer;
        }
    }
    
    answer=1;
    return answer;
}