투 포인터 two pointer 를 활용하여 문제 해결하기

투 포인터란?

 

배열 (정렬된 경우가 많음)에서 start과 end 두 곳에 포인터를 두고 순차적으로 조작하는 기법

 

일반적인 방식이 리스트에서 포인터를 하나 두고 타겟을 찾아나간다면, 

이것 양 방향에서 범위를 좁히거나 넓혀 나가는 식으로 문제를 해결하는 것

 

장점은?

for 문을 두 번 돌리면 O(n^2) 의 복잡도

투 포인터 방식으로 풀 수 있다면 O(n) 복잡도로 해결이 가능해짐

문제 예시

두수의 합

정수로 된 정렬된 리스트를 입력으로 받고 덧셈하여 target을 만들 수 있는 두 숫자의 인덱스를 출력하는 문제

(리트 코드의 문제는 정렬된 리스트가 아니지만, 여기서는 투 포인터 풀이를 위해서 정렬된 리스트도 조건 한정)

 

Example

Input: nums = [2,7,11,15], target = 9

Output: [0,1]

 

Constraints:

• 2 <= nums.length <= 103
• -109 <= nums[i] <= 109
• -109 <= target <= 109
• Only one valid answer exists.

def solution(lst, target):
    #포인터 설정하기
    left, right = 0, len(lst)-1
    # 둘이 만날 때까지만 동작
    while not left == right:
        if lst[left] +lst[right] < target:
            left += 1
        elif lst[left] +lst[right] > target:
            right -= 1
        else:
            return [left, right]

 

 

참고: <파이썬 알고리즘 인터뷰> 박상길 지음

         <이것이 코딩 테스트다 with Python> 39강 투 포인터 해설 동영상