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

문제 출처: 프로그래머스

프로그래머스

 

문제 설명

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

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

출처: 프로그래머스

---

시간을 고려해야 한다는 점을 제외하고는 그렇게 어려운 문제는 아니었다. 또 팰린드롬이라는 주제는 이미 다른 문제들에서도 많이 다뤘기 때문에 접근도 어렵지 않았다. 사실 문자열의 길이를 줄인다면 더 낮은 레벨을 부여 받지 않았을까 생각이 드는 문제였다.

 

문제를 푸는데 한 두번 밖에 시행착오를 겪지 않았지만, 다른 사람들의 풀이를 보니 내 풀이가 최적의 풀이는 아니었다.

 

<정답 코드>

def solution(s):
    answer = 1
    n = len(s)
    
    for i in range(n):
        for j in range(i+1, n):
            if s[i] == s[j]:
            	mid = (i+j) // 2
                aft = s[j:mid:-1]
                if (i+j) % 2 == 0:
                    pre = s[i:mid]
                else: 
                    pre = s[i:mid+1]
                    
                if pre == aft:
                    answer = max(answer, j-i+1)
                        

    return answer

접근은 아래와 같다.

1. S를 구성하는 모든 문자를 점검하면서 현재 값과 같은 값을 가지는 위치를 모두 찾은 다음 비교한다.
2. 문자열을 비교할 때는 split된 문자열의 길이가 짝수일 때와 홀수일 때가 다르다.
   1. 홀수일 때는 중앙값을 제외한 나머지가 대칭을 이루면 팰린드롬이다.
   2. 짝수일 때는 중앙값이 없으므로 전체가 대칭을 이루면 팰린드롬이다.
3.  가장 큰 값을 answer로 업데이트한다. 가장 짧은 팰린드롬의 길이는 한 단어 (ex. 'a')이므로 최소값이 1이 출력될 수 있도록 수정해야한다.

시행착오 부분은 처음에 팰린드롬은 길이가 홀수여야한다는 착각과, 최소 길이가 1이라는 점을 망각했기에 틀린 답을 제출했었다. 이 부분만 제거하니 문제는 풀렸다.

 

다만 제출된  답안의 실행시간이 1647ms로 크게 나왔다는 점이 살짝 걸렸다.

 

다른 사람들의 풀이를 살펴보니 DP로 접근한 사람도 있고, early stop 조건을 삽입한 사람도 있었다. 다양한 풀이가 있는 만큼 내 코드도 개선될 부분이 있을거라 생각한다.