두 포인터 (양쪽 끝)

Source: Dev.to

개요

이 패턴은 데이터 구조(배열 또는 문자열)의 양쪽 끝에서 시작하여 서로를 향해 이동하는 두 개의 포인터를 사용합니다. 주로 다음과 같은 경우에 사용됩니다:

• 양쪽 끝 모두에서 순서가 중요할 때
• 데이터가 정렬되어 있거나 대칭일 때
• 쌍이나 대칭 위치를 확인할 때
• 시간 복잡도를 O(N²) 에서 O(N) 으로 줄이고 싶을 때

포인터 설정

• left → 인덱스 0에서 시작
• right → 인덱스 n – 1에서 시작

반복 조건

left < right인 동안 계속합니다.

포인터 이동 로직

• 현재 조건이 만족되면: 답을 업데이트하고 포인터를 이동합니다.
• 값이 너무 작으면: left를 앞으로 이동합니다.
• 값이 너무 크면: right를 뒤로 이동합니다.

시간 및 공간

• 시간 복잡도: O(N)
• 공간 복잡도: O(1)

예시

예시 1: Two Sum (정렬된 배열)

문제:
정렬된 배열이 주어졌을 때, 합이 목표값과 같은 쌍이 존재하는지 판단합니다.

로직:

• 합이 목표값보다 작으면 left를 증가시켜 더 큰 합을 만듭니다.
• 합이 목표값보다 크면 right를 감소시켜 더 작은 합을 만듭니다.

def two_sum_sorted(nums, target):
    left = 0
    right = len(nums) - 1

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

        if current_sum == target:
            return True
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    return False

예시 2: 팰린드롬 검사

문제:
문자열이 팰린드롬인지 확인합니다.

로직:

• 대칭 위치에 있는 문자들이 일치해야 합니다.
• 불일치가 발생하면 즉시 False를 반환합니다.

def is_palindrome(s):
    left = 0
    right = len(s) - 1

    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1

    return True

예시 3: 최대 물 저장 용량(Container With Most Water)

문제:
두 개의 수직선을 선택해 x축과 함께 물을 가장 많이 담을 수 있는 용기를 찾습니다.

로직:

• 면적은 너비와 작은 높이에 의해 결정됩니다.
• 면적을 늘리기 위해 작은 높이를 가진 포인터를 이동합니다.

def max_area(height):
    left = 0
    right = len(height) - 1
    max_water = 0

    while left < right:
        width = right - left
        current_height = min(height[left], height[right])
        max_water = max(max_water, width * current_height)

        if height[left] < height[right]:
            left += 1
        else:
            right -= 1

    return max_water

예시 4: 제자리 배열 역순 (Reverse Array In‑Place)

문제:
추가 공간을 사용하지 않고 배열을 역순으로 만듭니다.

로직:

• 대칭 위치에 있는 요소들을 교환합니다.
• 포인터가 만날 때까지 안쪽으로 이동합니다.

def reverse_array(arr):
    left = 0
    right = len(arr) - 1

    while left < right:
        arr[left], arr[right] = arr[right], arr[left]
        left += 1
        right -= 1

    return arr

식별 체크리스트

다음 질문을 해보세요:

• 두 요소를 함께 비교하고 있나요?
• 양쪽 끝의 값에 관심이 있나요?
• 매 단계마다 한쪽을 버릴 수 있나요?
• 데이터가 정렬되어 있거나 대칭인가요?

답이 예라면 이 패턴이 적합합니다.

요약

• 두 포인터가 반대쪽 끝에서 시작합니다.
• 두 포인터 모두 안쪽으로 이동합니다.
• 각 반복마다 불가능한 경우를 제거합니다.

이 접근법은 깔끔하고 최적이며 이해하기 쉽습니다.