배열에서 섹션의 시작점과 끝점을 결정하고 시작점과 끝점을 기준으로 문제를 해결하는 방법을 두 개의 포인터라고 합니다. 문제를 보면 이해하기 쉽습니다.
예)
가장 긴 회문 하위 문자열을 인쇄하는 문제입니다. 회문은 앞으로 읽어도 뒤로 읽어도 같은 문자열입니다. 예를 들어 “aba”를 거꾸로 읽어도 팰린드롬인 “aba”입니다. 여기서 문제는 가장 긴 회문 하위 문자열을 찾는 것이므로 문제는 “babad”라는 문자열이 주어졌을 때 “bab” 또는 “aba”를 찾는 것입니다(둘 중 하나만 찾으면 됩니다). cbbd의 경우 답은 bb입니다.
설명)
팰린드롬은 좌우대칭이므로 팰린드롬의 중심점을 기준으로 좌우로 확대하여 팰린드롬임을 확인할 수 있다. 위의 예에서 보았듯이 회문의 길이는 홀수일 수도 있고 짝수일 수도 있으며 이 두 경우를 따로 취급하는 것이 편리합니다. 짝수의 경우 다음과 같이 시작점과 끝점을 중심으로 하여 팰린드롬인지 확인하면 편리합니다.
위와 같이 회문의 길이가 짝수인지 확인하려면 문자열의 길이가 2보다 크거나 같아야 합니다. 따라서 예외 처리가 필요합니다. 홀수일 경우 이렇게 펼쳐서 찾으시면 편리합니다
위와 같이 팰린드롬 길이가 홀수이면 L과 R 모두 “c”에서 시작하면 괜찮지만 팰린드롬 길이가 1이면 어차피 예외 처리가 되므로 3부터 시작하는 것이 의의가 없고 더 효율적이다.
따라서 다음과 같이 해결할 수 있습니다. (효율보다는 직관을 추구했습니다)
class Solution:
def longestPalindrome(self, s: str) -> str:
# 우선 길이가 2보다 작거나 같은 경우 예외 처리
if len(s) <=2 :
if s==s(::-1):
return s
return s(0) # 길이가 2이지만 팰린드롬이 아닌 경우 해당
# 투 포인터 사용한 팰린드롬 서치 함수 정의
def tp_search(L,R):
# 오른 쪽 범위를 벗어나거나 (밑에 for loop 참고) 팰린드롬이 아니면 길이 1인 스트링 리턴
if R == len(s) or s(L)!=s(R):
return s(L)
# 범위를 벗어나지 않고 팰린드롬인 경우 확장
while L>-1 and R<len(s) and s(L)==s(R):
L-=1
R+=1
return s(L+1:R)
longest="" # 가장 긴 팰린드롬 초기화
for i in range(len(s)-1):
# 가장 긴 팰린드롬 업데이트
longest = max(longest,tp_search(i,i+1),tp_search(i,i+2),key=len)
return longestTwo Pointer로 다음과 같은 문제도 해결할 수 있습니다.
참조: 파이썬 알고리즘 인터뷰: 95개의 알고리즘 문제를 풀어 코딩 테스트 완료