투 포인터 방법

2.1 투 포인터 방법의 정의

투 포인터 방법 — 이건 배열과 문자열의 다양한 문제를 해결하기 위해 사용하는 기술로, 두 개의 포인터(인덱스)를 사용해서 특정 규칙에 따라 데이터를 이동시키는 방법이야. 이 방법은 주어진 조건을 만족하는 요소 쌍, 부분 집합 등을 찾는 문제를 효율적으로 해결할 수 있어.

이 방법은 보통 데이터 구조의 반대쪽 끝에 두 포인터를 초기화하고 서로 마주 보거나 특정 규칙에 따라 이동하는 걸 의미해. 투 포인터 방법은 더 단순한 접근 방식에 비해 알고리즘의 시간 복잡도를 크게 줄일 수 있어.

주요 원칙

1. 두 포인터 초기화: 포인터는 배열이나 문자열의 시작과 끝에 설정할 수 있고, 문제에 따라 다른 인덱스에 설정할 수도 있어.
2. 포인터 이동: 포인터는 특정 규칙에 따라 이동해 (예: 두 포인터 모두 중앙으로 이동하거나 하나의 포인터만 앞으로 이동).
3. 조건 확인: 각 단계에서 포인터의 이동 또는 알고리즘 종료를 결정하는 조건을 체크해.

시간 복잡도:

O(n) — 대부분의 경우, 포인터 두 개가 배열을 한 번 이상, 하지만 합산해서 O(n) 번 이하로 지나감.

어떤 문제에서는 포인터의 초기 위치와 조건에 따라 시간 복잡도가 O(n log n) 이나 O(n^2)가 될 수도 있지만, 이는 드문 경우야.

투 포인터 방법으로 해결할 수 있는 문제들:

2.2 주어진 수의 합이 되는 배열 내 두 수 찾기

문제:

해결책:

하나의 포인터를 배열의 시작에, 다른 하나를 끝에 초기화해. 포인터 아래의 요소 합을 체크해:

• 합이 target과 같다면, 인덱스를 반환해.
• 합이 target보다 작다면, 왼쪽 포인터를 오른쪽으로 이동해.
• 합이 target보다 크다면, 오른쪽 포인터를 왼쪽으로 이동해.

시간 복잡도: O(n).

Python 코드 예시:

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        s = arr[left] + arr[right]
        if s == target:
            return left, right
        elif s < target:
            left += 1
        else:
            right -= 1
    return None
        

2.3 회문 확인

문제:

문자열이 회문인지 확인해.

해결책:

문자열의 시작과 끝에 포인터를 초기화해. 포인터 아래의 문자를 비교해:

• 문자가 같다면, 두 포인터를 서로 향해 이동시켜.
• 문자가 다르다면, 문자열은 회문이 아니야.

시간 복잡도: O(n).

Python 코드 예시:

def is_palindrome(s):
    left, right = 0, len(s) - 1
    while left < right:
        if s[left] != s[right]:
            return False
        left += 1
        right -= 1
    return True
        

2.4 정렬된 배열에서 중복 제거

문제:

정렬된 배열에서 중복을 제거해.

해결책:

하나는 결과 배열의 현재 위치를, 다른 하나는 모든 요소를 순회하는 두 포인터를 사용해:

• 현재 요소가 이전 요소와 다르다면, 결과 배열에 그것을 기록해.

시간 복잡도: O(n).

Python 코드 예시:

def remove_duplicates(arr):
    if not arr:
        return 0
    write_index = 1
    for i in range(1, len(arr)):
        if arr[i] != arr[i - 1]:
            arr[write_index] = arr[i]
            write_index += 1
    return write_index