코딩 인터뷰에서 이중 루프를 단일 패스로 압축하는 Two Pointers 패턴의 핵심 원리와 활용법을 정리한다

Context

브루트포스 방식의 이중 루프는 O(n²) 시간복잡도를 야기한다. 정렬된 배열 기반 문제에서 매 반복마다 불필요한 비교가 발생한다.

Technical Solution

• 정렬된 배열에서 양쪽 끝에 각각 포인터를 배치하고 합계에 따라 중앙으로 수렴시킨다
• 합계가 타겟보다 크면 오른쪽 포인터를 왼쪽으로, 작으면 왼쪽 포인터를 오른쪽으로 이동시킨다
• 동일 방향 포인터는 빠른 포인터가 탐색하고 느린 포인터가 고유값을 기록하는 역할을 분담한다
• 느린 포인터는 빠른 포인터보다 앞서갈 수 없으므로 데이터 간섭 없이 제자리 변환이 가능하다
• 각 반복에서 최소 하나의 후보를 제거하므로 최대 n회 연산으로 답을 보장받는다

Impact

Two Sum II 문제에서 시간복잡도가 O(n²)에서 O(n)으로 감소한다. Remove Duplicates 문제에서 공간복잡도가 O(n)에서 O(1)로 개선된다.

Key Takeaway

정렬된 입력 데이터, 쌍 찾기 요구사항, O(1) 공간 제약 중 하나라도 충족되면 Two Pointers 패턴 적용을 고려해야 한다.