[프로그래머스] 코딩테스트 연습 - 가장 긴 팰린드롬(Python)

문제 설명

문제

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

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

제한

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

입출력 예시

입출력 예

                  

 

s	answer
"abcdcba"	7
"abacde"	3

입출력 예 설명

입출력 예 #1
4번째자리 'd'를 기준으로 문자열 s 전체가 팰린드롬이 되므로 7을 return합니다.

입출력 예 #2
2번째자리 'b'를 기준으로 "aba"가 팰린드롬이 되므로 3을 return합니다.

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

프로그래머스

Level3 문제입니다. 펠린드롬 관련한 문제는 자주 접했던 유형 중 하나인 문제였습니다.

 

접근할 수 있는 방법으로는 DP 알고리즘을 사용하거나, 문자열을 순회하면서 푸는 방법을 생각해볼 수 있습니다. 저는 보다 직관적인 그리디한 방법으로 문자열을 순회하였습니다.

 

풀이는 코드를 토대로 설명해보겠습니다.

def solution(s):
    answer = 1
    
    for i in range(len(s)):
        for j in range(1,len(s)+1):
            if len(s[i:j]) < answer:
                continue
            if s[i:j] == s[i:j][::-1]:
                answer = max(answer, len(s[i:j]))


    return answer

먼저, 가장 유의해야 하는 실수 중 하나가 팰린드롬 길이의 최소값이 0인지 1인지를 결정하는 사안입니다.

저도, 질문검색을 통해서 안 사실인데, "abcde"와 같은 문자열은 펠린드롬 길이가 0 이 아니라 1이라고 합니다.

즉, 앞뒤를 뒤집어도 똑같지 않은 하나의 문자열도 최소 팰린드롬 길이를 1이라고 가정하는 셈이죠.

 

직관적으로 문자열을 순회하는데, 외부에 있는 반복문은 0부터 len(s)-1 까지 돌고, 내부에 있는 반복문은 1부터 len(s) 까지 돌도록 설정합니다.

문자열s의 i부터 j-1 까지 나타내는 문자열 s[i:j]이 이를 뒤집은 문자열 s[i:j][::-1]과 같다면, 그 문자열은 팰린드롬을 형성한다는 의미이므로 answer을 갱신합니다.

 

이 때, 첫 if문인 len(s[i:j]) < answer 을 안하니까, 효율성 테스트케이스 2번째 것이 시간초과가 나서, answer보다 탐색하려는 문자열의 길이가 작으면 불필요하게 순회하지 않도록 조건에 맞는 if문을 걸어두니 해결되었습니다.