코딩 인터뷰 마스터 : 파트 2 ( Two Pointers 패턴 )

Source: Dev.to

만약 이 시리즈의 Part 1을 읽었다면, 하나의 패턴이 느리고 비효율적인 풀이를 우아하고 최적화된 풀이로 바꿀 수 있다는 것을 이미 알고 있을 것입니다. 오늘은 같은 작업을 하지만 이번에는 Two Pointers(두 포인터) 패턴이라는 다른 도구를 사용해 보겠습니다.

이 패턴은 코딩 인터뷰 어디에서나 등장합니다. 한 번 인식하게 되면, 이전에 어려움을 겪었던 문제들에서도 이 패턴을 발견하게 될 것입니다.

두 포인터 패턴이란?

아이디어는 간단합니다: 데이터 구조를 순회할 때 하나의 인덱스를 사용하는 대신 두 개를 사용합니다. 이 포인터들은 특정 조건에 따라 배열(또는 문자열) 안을 이동하며, 중첩 루프 없이도 함께 답을 찾을 수 있게 도와줍니다.

첫 번째 변형을 실제로 보는 문제로 바로 들어가 보겠습니다.

Source:

문제 1 — Two Sum II: 입력 배열이 정렬되어 있음

이미 1‑인덱스이며 비내림차순으로 정렬된 정수 배열 numbers가 주어집니다. 두 수를 찾아서 그 합이 특정 target 값이 되도록 하세요. 두 수의 인덱스를 길이 2인 정수 배열 [index1, index2] 형태로 반환합니다.

완전 탐색 풀이

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i in range(len(numbers)):
            for j in range(i + 1, len(numbers)):
                if numbers[i] + numbers[j] == target:
                    return [i + 1, j + 1]   # 1‑인덱스 결과
        return []

시간 복잡도: O(n²) – 30 000개의 요소가 있는 배열에서는 최대 9억 번의 비교가 필요합니다.
결과: 큰 입력에 대해 시간 제한 초과(LeetCode). 실제 서비스에서는 대규모 데이터셋에 대한 2차 루프가 성능 병목이 됩니다.

두 포인터 패턴을 이용한 최적화

완전 탐색에서 놓친 핵심 통찰은 배열이 이미 정렬되어 있다는 점입니다. 이 힌트를 활용하면 두 포인터 패턴을 사용할 수 있습니다:

1. 시작(left)에 포인터 하나, 끝(right)에 포인터 하나를 놓는다.
2. 두 포인터가 가리키는 값의 합을 계산한다.
   • 합이 목표값과 같으면 → 인덱스를 반환한다.
   • 합이 너무 크면 → 더 작은 값을 얻기 위해 right를 왼쪽으로 이동한다.
   • 합이 너무 작으면 → 더 큰 값을 얻기 위해 left를 오른쪽으로 이동한다.

각 반복마다 후보가 하나씩 제거되고, 포인터가 수렴하면서 답을 찾거나(또는 존재하지 않음을 확인) 한 번의 패스로 종료됩니다.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left = 0                     # 배열의 시작
        right = len(numbers) - 1     # 배열의 끝

        while left < right:
            current_sum = numbers[left] + numbers[right]

            if current_sum == target:
                # 1‑인덱스 결과 반환
                return [left + 1, right + 1]

            if current_sum > target:
                # 합이 너무 큼 → 오른쪽 포인터를 왼쪽으로 이동
                right -= 1
            else:
                # 합이 너무 작음 → 왼쪽 포인터를 오른쪽으로 이동
                left += 1

        return []   # 문제에서 해답이 보장되지만, 좋은 습관

시간 복잡도: O(n)
공간 복잡도: O(1)

완전 탐색에 비해 크게 개선된 것이며, LeetCode에서도 문제 없이 통과합니다.

Variant 2 — 같은 방향 포인터

두 번째 변형은 반대쪽 끝에서 수렴하지 않습니다. 대신 두 포인터가 같은 쪽에서 시작해 같은 방향으로 이동하지만, 속도나 조건이 서로 다릅니다. 이는 배열을 제자리에서 재구성하거나 앞으로 스캔하면서 특정 패턴을 감지해야 할 때 완벽합니다.

고전적인 예제를 살펴보겠습니다.

Source: …

문제 2 — 정렬된 배열에서 중복 제거

정수 배열 nums가 비내림차순으로 정렬되어 있을 때, 제자리(in‑place) 로 중복을 제거하여 각 고유 요소가 한 번씩만 나타나도록 하세요. 고유 요소의 개수 k를 반환합니다.

직관적으로는 집합(set)을 사용해 고유값을 모은 뒤 배열을 다시 만드는 방법을 떠올릴 수 있지만, 이 문제는 제자리 해결과 O(1) 추가 공간을 명시적으로 요구합니다. 같은 방향으로 움직이는 두 포인터(일반적으로 slow와 fast 포인터) 기법이 효율적인 해결책을 제공합니다.

(해결 방법의 나머지는 다음 글에서 이어집니다.)

O(1) 추가 메모리를 이용한 제자리 해결법

집합을 사용하면 O(n) 공간이 필요해 목적에 어긋납니다.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        seen = set()
        result = []

        for num in nums:
            if num not in seen:
                seen.add(num)
                result.append(num)

        # This doesn't satisfy the in‑place constraint
        for i in range(len(result)):
            nums[i] = result[i]

        return len(result)

공간 제약을 위반할 뿐만 아니라, 불필요한 보조 데이터 구조를 만들게 됩니다.
Two Pointers 패턴을 사용하면 더 깔끔하고 제약을 만족하는 해결책을 얻을 수 있습니다.

최적화: 같은 방향 두 포인터

아이디어: slow 포인터는 다음 고유 요소를 기록할 위치를 가리키고, fast 포인터는 배열을 앞쪽으로 스캔하면서 새로운 고유 값을 찾습니다. fast가 slow가 가리키는 값과 다른 값을 발견하면 slow를 한 칸 앞당기고 그 위치에 새로운 값을 기록합니다.

class Solution:
    def removeDuplicates(self, nums: List[int]) -> int:
        # 'slow' marks the boundary of our unique‑elements section
        slow = 0

        # 'fast' scans ahead to discover new unique elements
        for fast in range(1, len(nums)):
            # When fast finds a value different from slow's position,
            # a new unique element has been discovered
            if nums[fast] != nums[slow]:
                slow += 1                  # Expand the unique section
                nums[slow] = nums[fast]    # Write the new unique value in place

        # slow is now the index of the last unique element
        # so the count of unique elements is slow + 1
        return slow + 1

• 시간 복잡도: O(n) — fast가 배열을 한 번만 순회합니다.
• 공간 복잡도: O(1) — 모든 작업을 제자리에서 수행하며 추가 데이터 구조를 사용하지 않습니다.

여기서 두 포인터가 팀처럼 작동한다는 점이 아름답습니다: fast는 탐색을, slow는 기록을 담당합니다. slow는 언제나 fast와 같은 위치이거나 그 뒤에 있을 수 있기 때문에 서로 충돌하지 않습니다.

언제 이 패턴을 사용해야 할까

• 정렬된 배열이나 문자열을 다룰 때 (반대 방향 포인터를 사용하라는 큰 힌트).
• 문제에서 조건을 만족하는 쌍(또는 삼중항)을 찾아야 할 때.
• O(1) 공간으로 배열을 제자리에서 재구성하거나 중복 제거해야 할 때.
• 완전 탐색 해결책이 동일한 선형 자료구조에 대해 중첩 루프를 사용한다면 — 이는 거의 항상 두 포인터를 사용해 O(n)으로 줄일 수 있다는 신호이다.

다음은? 연습

LeetCode에 가서 Two Pointers 문제 목록을 시도해 보세요 — 이 패턴으로 태그된 문제가 200개가 넘습니다. 직관을 기르기 위해 쉬운 문제부터 시작하고, 그 다음 중간 난이도로 넘어가세요.

다음에 시도해볼 몇 가지 좋은 문제

• Container With Most Water (중급) — 반대 방향 포인터.
• 3Sum (중급) — 외부 루프 안에 두 포인터.
• Linked List Cycle (쉬움) — 연결 리스트에서 빠른 포인터와 느린 포인터.

Note: Sliding Window 패턴과 마찬가지로 Two Pointers가 항상 유일한 유효한 접근법은 아닙니다. 정렬된 데이터, 제자리 제약, 쌍/부분집합 문제 등 특정 조건이 만족될 때 강력한 도구가 되지만, 사용하기 전에 이 패턴이 정말 맞는지 항상 고민하세요.

다음 기사에서 또 다른 코딩 패턴으로 뵙겠습니다!