팰린드롬 문제로 투포인터 익히기

팰린드롬이라고하면 우영우, 기러기, 토마토처럼 앞으로 읽어도 뒤로 읽어도 똑같이 읽히는 것을 말한다.

그럼 최장 팰린드롬을 구하는 문제로 투 포인터에 대해 알아보자.

가장 긴 팰린드롬 부분 문자열을 출력하라

리트코드 팰린드롬 문제

• 입력

  'babad'

• 출력

  'bab', 혹은 'aba'

우선 투 포인터란 알고리즘 문제를 풀때만 사용되는 스킬이다. left, right 두 개의 포인터를 잡고 각각 이동시키면서 문제를 해결한다.

팰린드롬 문제 같은 경우는 left와 right 포인터를 지정하고 left값과 right값이 일치하면 left-=1, right-=1을 한다.

left가 0보다 크거나 같을때까지 right이 전체 길이보다 작을때까지 그리고 left값과 right값이 같을때 까지 세가지 조건으로 반복문을 돌린다.

우선 포인터 확장 코드를 먼저 짜보면

def expand(left: int, right: int) -> str:
	while left>=0 and right <len(s) and s[left]==s[right]:
    	left-=1
        right+=1
    return s[left+1:right]

여기서 위의 세가지 조건으로 반복문의 조건을 걸엇고 리턴으로 s[left+1:right]을 해주는데 while문을 빠져나오기 전에 left-=1, right+=1을 해주므로 범위를 지정할때 저렇게 지정해준다.

그 다음 시간을 줄이기 위해 s의 길이가 2보다 작거나 s전체가 팰린드롬일 경우 바로 s를 리턴한다.

if len(s)<2 or s==s[::-1]:
	return s

여기서 s[::-1]은 s를 역순으로 뒤집는다는 의미이다.
그 후 팰린드롬이 짝수인 경우와 홀수인 경우를 나누어서 expand 함수를 호출한다.

result = ''
for i in (len(s)-1):
	result = max(result, expand(i, i+1), expand(i, i+2), key=len)
return result

다음과 같이 result에 ''을 입력하고 expand(i, i+1)처럼 짝수인 경우 expand(i, i+2)처럼 홀수인 경우로 나누어서 팰린드롬을 검사하고 매번 result와 길이를 비교하여 가장 긴 값을 result에 입력한다.

max함수도 key값을 입력하면 기준에 맞춰 최댓값을 뽑을수 있다.

출처 : 파이썬 알고리즘 인터뷰 (박상길 지음)