프로그래머스 [lv3] 가장 긴 팰린드롬 파이썬

문제 해결 포인트

1. s[::-1], 파이썬의 문자열 역전 메서드

2. for 문 범위잡기

 

 

정답 코드

def palindrome(s):
    if len(s) < 2 or s == s[::-1]:
        return True

def solution(s):

    if len(s) < 2 or s == s[::-1]:
        return len(s)

    for cur in range(len(s), 0, -1):
        for start in range(len(s)):
            currS = s[start: start + cur]
            if palindrome(currS):
                # result.append(len(s[start: start + cur]))
                return len(currS)
            if start + cur > len(s):
                break

 

 

접근 과정

palindrome() 함수를 따로 정의하였습니다.

인자로 들어오는 문자열이 팰린드롬인지 확인하여 true면 리턴합니다.

s[0] == s[-1]  조건이 맞을 때 s[1:-1] 로 슬라이싱하여, 다시 palindrome() 함수의 인자로 넣는 재귀방법을 택했습니다.

아래 주석 친 부분처럼 코드를 짰지만, 시간 초과가 발생했습니다.

def palindrome(s):
    if len(s) < 2 or s == s[::-1]:
        return True

    # 완벽한 로직 같았지만, 실은 연산 횟수만 늘려갔다.
    # if s[0] == s[-1]:
    #     return palindrome(s[1:-1])

 

 

하지만 가장 끝 자리 글자를 비교하며 재귀를 치기엔 시간복잡도에서 실패합니다. 다른 방법을 생각해야 합니다.

 

palindrome()에 처음 들어오는 문자열 s가 palindrome 한지 곧 바로 체크하는 것입니다. (재귀 대신)

파이썬의 매직 메소드 s[::-1]을 사용하여 기존 문자열과 뒤집어진 문자열을 비교하여 True일 때 리턴합니다.

 

그렇다면 palindrome()으로 던질 인자 s는 어떻게 정하게 되는 걸까요?

먼저 이중 for 문을 구현합니다.

안쪽 for문에서 start 변수로, 문자열 s의 시작점을 지정하고, 

바깥 for문에서는 cur 변수로, 문자열 s의 끝지점(범위)를 지정합니다.

 

이때 start + cur 의 범위가 인덱스 초과가 날 경우 break하여 start 변수를 0으로 초기화 할 수 있습니다.

 

cur 변수는 문자열 s의 길이 len(s)로 시작하여 1까지 내려갑니다.

그렇기 때문에 palindrome() 함수에서 true로 리턴되는 문자열이, 곧 가장 긴 팰린드롬이 됩니다.

def solution(s):

    if len(s) < 2 or s == s[::-1]:
        return len(s)

    for cur in range(len(s), 0, -1):
        for start in range(len(s)):
            currS = s[start: start + cur]
            if palindrome(currS):
                # result.append(len(s[start: start + cur]))
                return len(currS)
            if start + cur > len(s):
                break