[TP] Two Pointer Algorithm

이름 그대로 두 가지 포인터를 사용하여
문자열이나 배열(또는 리스트)에서 원하는 값을 찾거나
반복문을 써야 할 때 쓰는 방식

투포인터 알고리즘은 Two Pointer Algorithm 또는 Sliding Window라고 부른다.

1차원 배열이 있고, 이 배열에서 각자 다른 원소를 가리키고 있는 2개의 포인터를 조작해가면서
원하는 것을 얻는 형태이다.

코딩 테스트 문제를 풀다 완전 탐색으로 해결하다보면 시간 초과가 나는 문제가 종종 있다.

이러한 경우 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있다.

포인터는 크게 두가지 방식으로 쓰인다.

1. 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 형식
2. 또는 빠른 포인터(fast runner)가 느린 포인터(slow runner)보다 앞서는 형식

1. 중간에서 만나는 포인터

해당 방식을 설명하기 적절한 문제 : Two Sum (Sorted array)

작은 수부터 큰 수로 정렬된 배열 numbers와 숫자 targets가 주어진다.

이 배열 내에서 숫자 두 수의 합이 target인 두 수의 인덱스(1로 시작)를 출력하는 문제이다.

Test Case )

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

Output: [1, 2]

기본 탐색 알고리즘 : 이중 for 문

반복문 (loop) 두 개로 한 숫자와 모든 숫자를 차례대로 더해보는 방식이다.

테스트 케이스에서 찾으려는 두 수가 배열의 앞쪽에 있다면 타임 아웃에 걸리지 않겠지만,

만약 13010개의 0과 13008개의 9 사이에 숨어있는 2와 3을 찾고자한다면

outer loop을 13010번 돌고 13011번째 루프에서 target을 찾게 될 것이므로 각 루프에서

26020번 더하기를 실행했기에 타임 아웃이 될 것이다.

투 포인터 방식

타임 아웃에 걸리지 않는 방식으로 알고리즘을 수정한다면

앞에서 시작, 뒤에서 시작하는 두 포인터를 사용하면 시간 복잡도를 낮출 수 있다.

앞에서 시작하는 포인터 i와 뒤에서 시작하는 포인터 j

두 포인터가 만날 때까지 또는 원하는 값 target을 찾을 때까지 밑 과정을 반복합니다.

• 두 수의 합이 target보다 작으면 i 포인터를 앞으로 하나 이동 (i += 1)
• 두 수의 합이 target보다 크면 j 포인터를 뒤로 하나 이동 (j-=1)

따라서 다음 방식을 통해 기본 탐색 방식보다 훨씬 빠르고 효율적이게 원하는 값을 찾을 수 있다.

2. 토끼와 거북이

투 포인터의 다른 형식은 앞과 끝에서 시작하는 포인터가 아니라

두 포인터가 앞에서 시작하는데 속도가 다르게 움직이는 형식이다 (이름하여 fast runner와 slow runner).
주로 fast runner는 각 반복문마다 커지고 slow runner는 커지는 데에 조건이 있는 편으로 쓰인다.

 

해당 방식을 설명하기 가장 적절한 문제 : Remove Duplicates  

숫자가 들어있는 정렬된 배열에서 중복되는 숫자를 제거하는 문제입니다.

중복이 없는 새로운 배열의 길이를 출력하면 된다.

새로운 리스트를 만드는 게 아니라 리스트를 바꾸는 형식으로 해야 한다.

Test Case )

Input : nums = [0, 0, 1, 1, 1, 2, 2, 3, 3, 4]

Output: 5

 

def removeDuplicates(self, nums:List[int]) -> int:
	slow = 0
    for fast in range(1, len(nums)):
    	if nums[slow] != nums[fast]:
        	slow += 1
        	nums[slow] = nums[fast]
            
    return slow + 1

이 코드에서 두 포인터 slow와 fast는 각각 인덱스 0과 1에서 시작한다.

 

Outer loop에서 fast가 인덱스 1부터 시작에 쭉 움직이게 되어있다.

이때 slow 포인터는 조건이 맞아야지만 앞으로 이동 (slow += 1) 한다.

 

두 포인터가 가리키는 숫자가 다르다면 slow는 앞으로 이동을 한 후,

그 숫자를 fast 포인터가 가르키는 숫자로 바꿔준다.

 

fast 포인터가 먼저 '달리면서' 다른 숫자를 찾으면 slow포인터에게 알려줘서

slow가 바꿔주는 식으로 생각하면 된다.

 

이 loop를 반복하다 보면 배열이 nums = [0,0,1,1,1,2,2,3,3,4]에서

nums = [0, 1, 2, 3, 4, 2, 2, 3, 3, 4]로 바뀌고 slow+1이 중복된 숫자가 없는 길이로 출력하면 된다.

 

참조 : [Python] bisect 사용법👀 / 이분탐색 / 코딩테스트 (tistory.com)

[Python] bisect 사용법👀 / 이분탐색 / 코딩테스트