투 포인터란?
이번 글에서는 Two pointers technique (algorithm)을 설명해보도록 하겠습니다.
일단 이름 그대로 두 가지 포인터를 사용하여 문자열이나 배열(또는 리스트)에서 원하는 값을 찾거나 반복문을 써야 할 때 쓰기 좋은 방식입니다.
그냥 naive 방식인 그냥 탐색 (반복문)을 쓰다보면 시간 초과가 걸리는 경우가에 투 포인터를 사용하면 메모리와 시간 효율성을 높일 수 있습니다. 코딩 테스트를 보면 시간 복잡도를 낮출 수 있는 경우에는 일부로 테스트 케이스에 n이 정말 큰 (엄청 긴 배열이나 문자열)을 사용해서 Time out을 걸리게 하는 케이스가 많습니다.
포인터는 크게 두가지 방식으로 쓰입니다.
- 앞에서 시작하는 포인터와 끝에서 시작하는 포인터가 만나는 형식
- 또는 빠른 포인터 (fast runner)가 느린 포인터 (slow runner) 보다 앞서는 형식
밑에서 각 두 형식에서 유명한 연습 문제를 풀며 설명해보겠습니다.
형식 1: 중간에서 만나는 포인터
리트코드의 Two sum (sorted array) 문제를 써서 설명해보겠습니다. (문제 링크 난이도: ★)
작은 수부터 큰 수로 정렬된 배열 numbers와 숫자 target가 주어집니다.
이 배열 내에서 숫자 두 수의 합이 target인 그 두 수의 인덱스(1으로 시작)를 출력하는 문제입니다.
테스트 케이스 예)
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
기본 탐색 알고: 이중 for문 사용
반복문 (loop) 두 개로 한 숫자와 모든 숫자를 차례대로 더해보는 방식입니다.
첫 숫자(i=0)인 3을 다음 숫자 (j=1) 24랑 더해보고 합이 target이 아니면
다음 숫자 (j=2) 50이랑 더해보고 또 아니네
다음 숫자 (j=3)랑 더해보고... 이렇게 배열에 있는 모든 숫자랑 더해보고 target이 나오면 인덱스를 출력하는 기본적인 알고입니다.
테스트 케이스에서 배열이 짧거나 배열이 길어도 찾으려는 두 수가 배열의 앞쪽에 있다면 타임 아웃이 안 걸리겠지만..
이런 코드를 아웃시키려는 테스트 코드를 보면: (target=5)
이렇게 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 문제를 한번 보겠습니다. (문제 링크 난이도: ★)
숫자가 들어있는 정렬된 배열에서 중복되는 숫자를 제거하는 문제입니다. 중복이 없는 새로운 배열의 길이를 출력하면 됩니다. 새로운 리스트를 만드는 게 아니라 리스트를 바꾸는 형식으로 해야 합니다.
테스트 케이스 예)
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이 중복된 숫자가 없는 길이로 출력하면 됩니다.
투 포인터 연습 문제