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

문제

문제 설명

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

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

 

제한사항

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

입출력 예시

s	answer
"abcdcba"	7
"abaced"	3

문제: 프로그래머스 스쿨 - 연습문제 - 가장 긴 팰린드롬

---

문제 풀이

유의사항

• s의 길이가 2,500이하 이므로, O(N^2)으로 문제를 풀 수 있다.
• 팰린드롬을 검사하는 함수를 선언하여 문제를 풀면, 쉽게 풀 수 있다.
  • 팰린드롬을 검사하는 알고리즘은 O(N)이다.
  • 파이썬에서 특정 문자열을 뒤집는 방법에는 몇가지가 있으나, 가장 간단한 방법은 아래와 같다.

str[::-1]

풀이

• 핵심 아이디어: 주어진 문자열에 대한 모든 substring에 대해 팰린드롬인지 검사한 후, 그 중 가장 긴 substring의 길이를 출력하면 된다.
  • 팰린드롬을 검사하는 방법: 문자열을 뒤집었을 때, 원래와 동일하다면 팰린드롬이다.

def isPalindrome(str: str):
    if str == str[::-1]:
        return True
    return False

 

---

전체 코드

def isPalindrome(str: str):
    if str == str[::-1]:
        return True
    return False

def solution(s):
    answer = 1

    for start in range(len(s)):
        for end in range(len(s), start-1, -1):
            if(isPalindrome(s[start: end])):
                answer = max(answer, end - start)
    
    return answer

print(solution("abcdcba"), "expected: 7")
print(solution("abacde"), "expected: 3")