[Programmers]Python_가장 긴 팰린드롬

문제

 

문제 설명

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

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

 

제한사항

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

코드

def solution(s):
    result = []
    for left in range(len(s)): #start point
        for right in reversed(range(left, len(s) + 1)): #end point
            test = s[left:right]
            #팰린드롬이라면 해당 문자 길이를 추가
            if test == test[::-1]:
                result.append(right - left)
    return max(result) #가장 긴 문자 길이 return

 

진행 과정

 

예제 #1

s = "abcdcba"

 

접근은 간단하다. 시작점을 기준으로 끝까지 순회하고 시작점을 한 칸 옮기고 다시 끝까지 순회하는 반복이다.

해당 예제라면 a를 시작으로 a, ab, abc, abcd, abcdc .... abcdcba 까지 팰린드롬 확인후 b를 시작으로 다시 bc, bcd, bcdc .... bcdcba 까지 팰린드롬을 확인하는 반복이다.

 

이중 for문을 사용한 위 코드의 팰린드롬일때 left, right 값과 해당 길이의 출력은 다음과 같다.

 

1) left = 0 right = 7 length = 7 #abcdcba
2) left = 0 right = 1 length = 1 #a
3) left = 0 right = 0 length = 0
4) left = 1 right = 6 length = 5 #bcdcb
5) left = 1 right = 2 length = 1 #b
6) left = 1 right = 1 length = 0
7) left = 2 right = 5 length = 3 #cdc
8) left = 2 right = 3 length = 1 #c
9) left = 2 right = 2 length = 0
10) left = 3 right = 4 length = 1 #d
11) left = 3 right = 3 length = 0
12) left = 4 right = 5 length = 1 #c
13) left = 4 right = 4 length = 0
14) left = 5 right = 6 length = 1 #b
15) left = 5 right = 5 length = 0
16) left = 6 right = 7 length = 1 #a
17) left = 6 right = 6 length = 0

 

18) result = [7, 1, 0, 5, 1, 0, 3, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0]

19) return 7 #최댓값 return

---

2021.05.25 추가

def solution(s):
	#길이가 2미만이거나 s가 팰린드롬이면 s의 길이를 리턴
    if len(s) < 2 or s == s[::-1]:
        return len(s)
    
    n = len(s)
    def check(left, right):
    	#양쪽으로 확장하며 팰린드롬 검사 진행
        while left >= 0 and right < n and s[left] == s[right]:
            left -= 1
            right += 1
        return len(s[left + 1:right])
    
    answer = 1
    for i in range(len(s) - 1):
    	#홀수길이일때와 짝수길이일때 체크하여 가장 긴 길이를 answer에 저장
        answer = max(answer, check(i, i), check(i, i + 1))
    return answer

예를 들어 s = "abacde"라고 한다면 인덱스 0인 a부터 시작하여 "a"와 "ab"가 팰린드롬인지 check함수를 통해 검사하는 것이다. 여기서 팰린드롬의 길이가 홀수일 때와 짝수일 때 두 가지를 고려해야 한다. 홀수의 길이를 가질 경우 "aba"와 같이 팰린드롬이 되지만 짝수일 경우 "abba"와 같이 되기 때문이다. 이게 무슨 말이냐면 홀수일 경우 'b'부터 양쪽으로 확장을 했을 때 팰린드롬인 것을 판단하지만 짝수일 경우 'bb'부터 확장하여 'abba'가 팰린드롬이라는 것을 판단할 수 있다는 것이다.

 

이어서 첫 번째 인덱스 0부터 진행한다면 다음과 같다.

- index=0, check(0,0)

s[left] s[right] = a a
s[left + 1:right] = a

 

- index=1, check(1,1)
s[left] s[right] = b b
s[left] s[right] = a a
s[left + 1:right] = aba

 

- index=2, check(2,2)
s[left] s[right] = a a
s[left + 1:right] = a

 

- index=3, check(3,3)
s[left] s[right] = c c
s[left + 1:right] = c

 

- index=4, check(4,4)
s[left] s[right] = d d
s[left + 1:right] = d

 

짝수일 때의 팰린드롬은 아예 없어서 출력값이 안나온다....