ch6-6(leetcode 5). 가장 긴 팰린드롬 부분 문자열

* 해당 포스트는 <파이썬 알고리즘 인터뷰> 공부 후 정리 목적으로 작성되었습니다. *

 

leetcode 5번 ( https://leetcode.com/problems/longest-palindromic-substring/ )

 

풀이방법 1.

투 포인터를 사용하면 된다. 보통 투 포인터는 입력의 양 끝에서 중앙으로 모이는 형태를 생각하지만, 반대로 특정 기준점에서 양쪽으로 퍼져 나가는 형태도 가능하다. 

 

left, right 포인터를 어느 지점을 기준으로 양쪽으로 퍼져 나갈지를 정하는 시작점이라고 보자. 

 

left 포인터는 문자열의 0번째 인덱스부터 len(string)-2번째 인덱스까지를 시작점으로 둘 수 있다. 반면 right 포인터는 문자열의 1번째 인덱스부터 len(string)-1번째 인덱스까지를 시작점으로 둘 수 있다. 

 

left, right 포인터를 각각 시작점으로 정했다면 해당 시작점을 기준으로 left 포인터는 왼쪽으로 한 칸씩, right 포인터는 오른쪽으로 한 칸씩 이동하며 확장한다. left와 right 포인터의 값이 같다면 계속 확장하고, 그렇지 않다면 지금까지의 left와 right 포인터 사이에 위치한 문자열을 반환한다. 

 

문자열을 확장하며 팰린드롬을 찾아서 리턴하는 로직과, 가장 큰 팰린드롬을 찾는 로직을 구분하면 코드가 더 간결할 것이다. 따라서 앞의 로직은 함수 내부의 함수로 따로 선언해 주자.

교재에서는 expand(left, right)라는 내부 함수로 선언했다. 

 

이때 문자열 슬라이싱 인덱스가 [a:b]일 경우, 실제로 반환되는 문자열은 a번째 인덱스부터 b-1번째 인덱스이므로 주의해야 한다. 

또한, left와 right 포인터의 현재 위치는 포함하지 않고, 그 사이에 있는 문자열만 리턴해야 하므로, expand() 함수는 다음과 같이 리턴한다. 

return string[left+1, right]

 

또한 팰린드롬의 길이는 홀수일 수도, 짝수일 수도 있다. 홀수일 경우 가운데 문자 하나로부터 양쪽으로 확장해야 하고, 짝수일 경우 나란히 있는 문자 두 개를 기준으로 양쪽으로 확장해야 한다. 

따라서 홀수 팰린드롬을 찾으려면 left와 right 포인터가 1칸 차이여야 하고, 짝수 팰린드롬을 찾으려면 두 포인터가 2칸 차이여야 하겠다. 

expand(i, i+1)	# odd
expand(i, i+2)	# even

 

문제에서는 가장 긴 팰린드롬을 반환하라고 했으므로, 가장 긴 팰린드롬을 저장할 변수도 필요하다. 

여러 개의 변수를 파라미터로 받을 수 있는 max() 함수를 사용하되 기준을 정하지 않으면 가장 긴 팰린드롬이 아니라 알파벳 순서 상 가장 먼저인 팰린드롬이 리턴될 것이다. 

따라서 max() 함수에도 key 파라미터 값으로 len 함수를 할당해서, 알파벳 순서가 아니라 팰린드롬의 길이를 기준으로 하도록 바꿔 준다. 

result = max(result, expand(i, i+1), expand(i, i+2), key=len)
return result