프로그래머스 가장 긴 팰린드롬

문제 설명

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

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

제한사항

• 문자열 s의 길이 : 2,500 이하의 자연수
• 문자열 s는 알파벳 소문자로만 구성

def palindrome(string):
    if len(string)<=1:
        return True
    
    if string[0]==string[-1]:
        return palindrome(string[1:-1])
    else:
        return False
    
def solution(s):
    answer = 0
    check=False
    for i in range(len(s),0,-1):
        for j in range(len(s)):
            cut=s[j:j+i]
            check=palindrome(cut)
            if check==True:
                return len(cut)
            if j+i>=len(s):
                break
                

    return answer

처음 코드는 재귀를 통해서 가장 긴 문자열에서 순차적으로 길이를 줄여가며 palindrome을 검사했습니다.

하지만 이럴경우 정확도는 전부 통과가 되지만 효율성에서 1개의 케이스가 런타임이 발생합니다..

def palindrome(string):
    if len(string) <= 1:
        return True

    start = 0
    end = len(string) - 1

    for i in range(len(string) // 2):
        if string[start + i] != string[end - i]:
            return False

    return True


def solution(s):
    answer = 0
    check = False
    for i in range(len(s), 0, -1):
        for j in range(len(s)):
            cut = s[j:j + i]
            if palindrome(cut) == True:
                return len(cut)
            if j + i >= len(s):
                break

    return answer

위와 같은 런타임을 없애기 위해 가장 긴 문자열에서 길이를 줄여가며 palindrome을 검사하는 것은 동일하지만

재귀를 통한것이 아닌 주어진 문자열의 반 만큼을 for문을 통해 검사를 하여 효율성을 통과했습니다.

 

사용언어: python

문제출처: programmers.co.kr/learn/courses/30/lessons/12904

코딩테스트 연습 - 가장 긴 팰린드롬