[알고리즘] 투포인터

투포인터

• 배열이나 리스트에서 ‘두 개의 포인터’를 사용하여 ‘특정 조건을 만족하는 부분 구간’을 효율적으로 탐색하는 알고리즘
• 보통은 왼쪽 포인터와 오른쪽 포인터를 사용하며, 이들은 각각 탐색 범위의 시작과 끝을 가리킴
• 탐색 범위 내에서 특정 조건을 만족하는 요소를 찾거나, 조건을 만족하는 부분 배열의 길이 등을 계산하는 데 사용
• 투 포인터의 수행 단계
  1. 배열 또는 리스트의 시작 위치에 첫 번째 포인터와 두 번째 포인터를 설정
  2. 두 포인터 사이의 구간을 조사하고 조건을 확인
  3. 조건을 만족할 경우, 원하는 결과를 얻었으므로 알고리즘을 종료
  4. 조건을 만족하지 않을 경우, 첫 번째 또는 두 번째 포인터를 이동
  5. 다시 2번 단계로 돌아가 반복

시간 복잡도

• 일반 : O(N)
• 정렬 후 투포인터 : O(NlgN)

자료 구조

• 배열 혹은 리스트

예시 코드

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int,input().split()))
ans = sys.maxsize
left, right = 0, n - 1

arr.sort()
x, y = 0, n - 1

while x < y:
    mix = arr[x] + arr[y]
    if abs(mix) < ans:
        ans = abs(mix)
        left = x
        right = y

    if mix > 0:
        y -= 1
    elif mix < 0:
        x += 1
    else:
        break

print(arr[left], arr[right])