투포인터

가능한 조합을 하나하나 찾는 방식인 브루트 포스(brute-force)를 사용할 수 도 있지만, 이는 배열의 크기가 n일 때 O(n^2)의 시간복잡도를 갖기 때문에 비효율적입니다.
이러한 비효율을 해결하기 위해 투포인터 알고리즘을 사용할 수 있습니다.
두 포인터(Two Pointer) 알고리즘은 두 개의 포인터(인덱스)를 사용하여 문제를 해결하는 기법입니다.

1. 양쪽 끝에서 두 포인터가 좁혀오는 방식

• 미리 정렬 필요!
• ex) 두 요소의 합이 특정 수와 일치하는 쌍을 구하는 문제

def two_pointer_sum(arr, target):
    arr.sort() # 먼저 배열을 정렬해야한다
    left, right = 0, len(arr)-1
    result_pairs = [] # 여러 쌍이 있을 경우를 대비

    while left < right: # 두 포인터가 교차하기 전까지 반복
        current_sum = arr[left] + arr[right]
        if current_sum == target:
            result_pairs.append([arr[left], arr[right]])
            left += 1

        elif current_sum < target:
            left += 1 # 더 큰 수 필요

        else: # current_sum > target
            right += 1 # 더 작은 수 필요

        return result_pairs if result_pairs else [] # 찾은 쌍들 또는 빈 리스트 반환

시간복잡도: 정렬 O(nlogn) + 스캔 O(n) -> O(nlogn)

2. 한쪽에서 두 포인터가 같은 방향으로 이동하는 방식(슬라이딩 윈도우 방식)

• 1번 방식과 다르게 미리 정렬이 필요하지 않음
• ex) 연속된 부분의 합이 target 이상인 가장 짧은 구간 찾는 문제

def sliding_window_min_length(arr, target_sum):
    left = 0
    current_sum = 0
    min_length = float('inf') # infinity(무한으로 큰 수)로 초기화

    for right in range(len(arr)):
        current_sum += arr[right] 

        
        while current_sum >= target_sum and left <= right:
            min_length = min(min_length, right - left + 1) # 길이 비교 -> 최소 길이 갱신
            current_sum -= arr[left] # 기준점(left 포인터)을 한칸 오른쪽으로 옮기기 위해 left값 빼기
            left += 1 # left값을 뺐으므로 left 위치 오른쪽으로 1칸 이동

    return min_length if min_length != float('inf') else 0  # 삼항연산자
                                                            # min_length가 갱신된 값이면 해당 값 반환
                                                            # target_sum 이상이 되는 구간이 없으면 min_length가 갱신되지 않으므로 
                                                            # 0 반환

시간복잡도: O(n)