프로그래머스 - 가장 긴 팰린드롬 [Python]

 문제

 

 

 

 

 문제 상황

 

- 주어진 문자열 내에 존재하는 회문을 찾아 그 가장 긴 길이를 반환하는 문제이다.

 

 

 

 해결 전략

 

- 주어진 조건이 2,500자로 O(N^2)을 해도 6,250,000로 매우 안정적인 범위이다. 회문을 검사하는 함수를 만들고 검사할 시작점과 끝점을 탐색하며 양 끝이 같아질 경우만 그 사이 리스트를 회문 검사 하였다.

 

 

 

 코드

 

def is_palindrome(lst):
    if len(lst)%2 == 0 and lst[:len(lst)//2] == lst[len(lst)//2:][::-1]: return True
    elif len(lst)%2 == 1 and lst[:len(lst)//2] == lst[(len(lst)//2)+1:][::-1]: return True
    return False    
 
 
def solution(s):
    # 최소 한자리이므로
    max_len = 1
    for i in range(len(s)-1):
        for j in range(i, len(s)):
            if s[i] == s[j] and is_palindrome(s[i:j+1]):
                if j-i+1 > max_len:
                    max_len = j - i + 1
    return max_len

 

 

 해설

 

- 문자를 순회하면서 시작점을 잡고 그 뒤에 문자열을 탐색하며 같아지는 지점에서 회문 검사를 한다.

 

- solution은 O(N^2)이므로 속도는 문제가 없다.

 

 

 

 새로 학습한 것 & 실수 

 

- 가장 마지막에 max값 임에도 갱신하는 조건을 넣지 않았다. 더 큰 요소만 넣어야하는데 그걸 빼먹어 답이 무조건 1이 나올 수 밖에 없었다.

 

 

 

 

출처 - https://programmers.co.kr/learn/courses/30/lessons/12904