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

Problem : https://school.programmers.co.kr/learn/courses/30/lessons/12904

프로그래머스

Status : Solved

Time : 00:09:49

 

---

 

문제 설명

 

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

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

 

입력 및 출력

 

제한사항

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

 

입출력 예

s	result
"abcdcba"	7
"abacde"	3

 

 

---

 

풀이

단순히 모든 부분문자열에 대해 펠린드롬인지를 검사해 보는 브루트 포스 방법도 있겠지만(나중에 이 방법도 통과되는 걸 알았다) 좀 더 빠른 시간 내에 풀이해보픈 마음에 다른 방법으로 풀이하였다.

어떤 펠린드롬 문자열에서 양 끝에 같은 문자가 더해지면 그 문자열 역시 펠린드롬이 된다는 점을 이용할 수 있다. 즉 홀수길이 펠린드롬의 경우 길이 1의 문자열을 중심축으로 좌우가 동일한지 재귀적으로 검사해나가면 되며, 짝수 길이 펠린드롬은 두 개의 같은 문자로 이루어진 길이 2의 문자열을 중심축으로 하면 된다.

 

풀이 코드

def solution(s):
    answer = 1
    length = len(s)
    for i in range(length) :
        if i < length - 1 and s[i+1] == s[i] :
            tmp = 0
            l, r = i, i+1
            while -1 < l < r < length and s[l] == s[r] :
                tmp += 2
                l -= 1
                r += 1
            answer = max(answer, tmp)
        if 0 < i < length - 1 :
            tmp = 1
            l, r = i-1, i+1
            while -1 < l < r < length and s[l] == s[r] :
                txqmp += 2
                l -= 1
                r += 1
            answer = max(answer, tmp)

    return answer

풀이 완료!