[알고리즘] 투 포인터 (+LeetCode 5)

배열에서 어떤 구간의 시작점과 끝점을 정하고, 시작점과 끝점을 기준으로 어떠한 문제를 푸는 방법을 투 포인터라고 부른다. 문제를 보면서 이해하는 것이 쉽다.

 

예제)

Longest Palindromic Substring - LeetCode

가장 긴 팰린드롬 부분 문자열을 출력하는 문제. 팰린드롬은 앞으로 읽어도 뒤로 읽어도 같은 문자열을 말한다. 예를 들어 "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 longest

다음 문제들도 투포인터로 풀 수 있다:

3Sum - LeetCode

Trapping Rain Water - LeetCode

 

Ref: 파이썬 알고리즘 인터뷰: 95가지 알고리즘 문제 풀이로 완성하는 코딩 테스트