투 포인터

개요

‘투 포인터’는 이름 그대로 2개의 포인터¹를 사용해 배열, 리스트, 문자열 같은 자료구조를 보다 효율적으로 탐색하는 기법이다.

예시

대표적인 문제로 정렬된 배열에서 합이 특정값 S가 되는 두 원소쌍이 존재하는지 구하는 문제가 있다.

단순하게 생각하면 이중 반복문을 통해 모든 가능한 합을 구하고, 그 합이 S인지 확인하는 방법이 있다. 이 경우의 시간복잡도는 $O(N^2)$이 된다.

투 포인터를 사용하면 $O(N)$만에 해결할 수 있다.

각각의 포인터를 배열의 양쪽 끝을 가리키도록 한다. (각각 left, right라고 지칭) 그리고 각 포인터가 가리키는 원소의 합이 S보다 크다면 right 포인터를 left쪽으로 옮기고, 작다면 left를 right으로 옮긴다.

public boolean twoSum(int[] arr, int target) {
	int left = 0;
	int right = arr.length - 1;
	
	while (left < right) {
		int sum = arr[left] + arr[right];
		
		if (sum == target)
			return true;
			
		if (sum < target)
			left++;
			
		if (sum > target)
			right--;
	}
	
	return false;
}

각각의 포인터를 한 쪽 방향으로만 이동시키기 때문에, 방문했던 원소는 다시 방문하지 않는다. 그래서 전체 시간복잡도가 $O(N)$이 된다.

참고자료

• geeksforgeeks, Two Pointers Technique, 2025.09.15, https://www.geeksforgeeks.org/dsa/two-pointers-technique/

Footnotes

1. 메모리의 주소를 저장하는 포인터가 아니라, 말 그대로 ‘가리킨다’는 의미에서 사용. ↩