문제 설명

※ 주의

본 문제는 일부러 시간복잡도가 오래 걸려도 정답이 나오도록 제한 시간이 넉넉하게 설정되어 있습니다. 본 문제를 정말 빠른 알고리즘으로 풀려면 구글에서 longest palindrom subsequence로 검색을 해보세요.

앞뒤를 뒤집어도 똑같은 문자열을 팰린드롬(palindrome)이라고 합니다. 문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

예를들면, 문자열 s가 abcdcba이면 7을 return하고 abacde이면 3을 return합니다.

제한사항
  • 문자열 s의 길이 : 2500 이하의 자연수
  • 문자열 s는 알파벳 소문자로만 구성
입출력 예
s answer
abcdcba 7
abacde 3
입출력 예 설명

입출력 예 #1 4번째자리 ‘d’를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2 2번째자리 ‘b’를 기준으로 aba가 팰린드롬이 되므로 3을 return합니다.

나의 풀이

소스

def palindrom(string):
    if string == string[::-1]:
        return True
    else:
        return False


def get_substring_combination(origin_string, hope_length):
    result_arr = []

    for i in range(len(origin_string) - (hope_length - 1)):
        sub_string = origin_string[i:i + hope_length]
        result_arr.append(sub_string)

    return result_arr


def solution(s):
    answer = 0
    s_length = len(s)

    while s_length > 0:
        sub_s = get_substring_combination(s, s_length)

        for sub in sub_s:
            if palindrom(sub):
                return len(sub)

        s_length -= 1

    return answer

설명

가장 큰 단어부터 줄여가는 방식인데,

팰린드롬인지 체크하면서, 글자 수가 하나 줄은 단어의 조합을 구해간다.

그래서 팰린드롬이 되면 해당 길이 리턴.

긴 길이를 구하라고 하였으므로 단어에서부터 하나씩 줄여가는 방식 사용.

다른사람의 풀이

def is_palindrome(s, start, end):
    for i in range((end - start) // 2 + 1):
        if s[start + i] != s[end - i]:
            return False

    return True


def solution(s):
    for answer in range(len(s), 0, -1):
        start = 0
        end = answer - 1

        while end < len(s): 
            if is_palindrome(s, start, end):
                return answer
            start += 1
            end += 1

    return 1