[프로그래머스] 가장 긴 펠린드롬

문제 설명

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

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

제한사항

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

---

입출력 예

sanswer

"abcdcba"	7
"abacde"	3

입출력 예 설명

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

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

 

 

오답노트

재귀라고 생각하고 풀어서그런가 어떻게하면 시간을 줄일지 고민하며 시간을 많이 보냈던 문제.

def solution(s):
    def check(s,ans):
        if len(s) == 2:
            return 0

        mid_idx = len(s) // 2
        for i in range(mid_idx):
            if s[i] != s[len(s)-i-1]:
                testa =  check(s[:-1],ans)
                testb = check(s[1:],ans)
                return max(testa,testb)
        else:
            if ans < mid_idx:
                return len(s)
    answer = check(s,-1)
    return answer

print(solution("cdeaba"))

내가 짯지만 참 시간 많이 쓰게 생겼다..

장렬히 전사한 나의 코드

 

다른 사람의 코드를 참조하여 '완전탐색'임을 알게 되었고, 깔끔하게 문제를 풀 수 있었다.

def solution(s):
    max_num = 1 # 자연수라고 문제에 적혀있다. -1로 해서 한번 더 틀렸었음. 조심하자!
    for i in range(len(s)-1):
        for j in range(i+1,len(s)+1):
            test = s[i:j]
            if test == test[::-1]:
                if max_num < len(test):
                    max_num = len(test)
    return max_num


print(solution("abcdcba"))

 

오늘도 참 부족한 하루였다..^^