[코딩 테스트] 프로그래머스 - 가장 긴 팰린드롬 (Lv.3) in Python

문자열 s가 주어질 때, s의 부분문자열(Substring)중 가장 긴 팰린드롬의 길이를 return 하는 solution 함수를 완성해 주세요.

 

예시: s = "abcdcba" // answer = 7

예시: s = "abacde" // answer = 3

 

 

더 자세한 문제설명 - programmers.co.kr/learn/courses/30/lessons/12904 

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

 

풀이

- 처음에는 문자열의 index를 하나씩 증가시켜가며 palindrome의 신호가 나타날 때

    1. s[i] == s[i+1]일 때 (ex. 'aa')

    2. s[i] == s[i+2]일 때 (ex. 'aba') 

  부터 palindrome의 길이를 세는 식으로 접근했는데,

  예외 처리가 너무 많아 복잡했다. ㅠㅠ

 

- 그래서 결국 문자열의 처음부터, (0부터 len(s)개)의 단어씩 잘라, 그 substring이  palindrome인 지 확인하고,

  맞다면 그 길이를 answer에 넣어주는 무식(?)하지만 구현하기 쉬운 방법으로 풀었다.

 

 

코드구현

 

def isPalindrome(s):
    if s == s[::-1]:
        return True
    else:
        return False
        
        
def solution(s):
    answer = 1
    
    for checkRange in range(len(s), 1, -1):
        for startIndex in range(len(s)):
            print(checkRange, startIndex, s[startIndex:startIndex+checkRange])
            if startIndex + checkRange > len(s):
                break
            if isPalindrome(s[startIndex:startIndex+checkRange]):
                answer = max(answer, checkRange)
                
    return answer

 

- 이 때, 반복문의 최대 수행 횟수는 (문자열 s의 길이) ^ 2가 되겠다. 다만 문제에서

• 문자열 s의 길이는 최대 4,500

으로 주어졌기 때문에, 4500 ^ 2 = 20,250,000으로 파이썬 효율성 테스트의 마지노선이라 생각되는 1억보다 훨씬 작기 때문에 괜찮다.

 

- 다른 분들의 코드에서, 정말 멋지게도 재귀함수로 구현한 분들이 많더랜다. 가장 따봉을 많이 받은 다움 풀이

def solution(s):
	return len(s) if s == s[::-1] else max(solution(s[:-1]),solution(s[1:]))  

를 옮겨본다 ㅠuㅜ (현재 이 풀이는 효율성 테스트를 통과하지 못하고, memoization으로 recursion depth를 줄여야 한다)

재귀함수를 잘 쓰시는 분들을 보면 경외심이 든다.