투 포인터(Two Pointers)

리스트에 순차적으로 접근해야 할 때 두 개의 점 위치를 기록하면서 처리하는 알고리즘

정렬되어있는 두 리스트의 합집합에도 사용된다.
merge sort의 기초가 되기도 함.

해당 알고리즘으로 단순 반복문 사용보다 메모리, 소요 시간을 아낄 수 있음.

크게 두 가지의 포인터 사용 방법 존재
1. 앞에서 시작하는 포인터 + 끝에서 시작하는 포인터
2. 빠른 포인터가 느린 포인터를 앞서는 형식(추월하는 느낌)

해결할 수 있는 문제

백준 2473
https://www.acmicpc.net/problem/2473

백쥰 14719

문제 풀이

[1] 백준 2473

n = int(input())
arr = sorted(list(map(int, input().split()))) # 오름차순 정렬

cnt = float('inf')
for i in range(n-2):
    b = i + 1   # 크기가 작은 포인터
    c = n-1     # 크기가 큰 포인터
    while b != c:
        value = arr[i] + arr[b] + arr[c]
        if abs(value) < cnt:
            cnt = abs(value)
            ans = sorted([arr[i], arr[b], arr[c]])
            if not value:
                print(*ans)
                exit()
        if value > 0:
            c -= 1
        elif value < 0:
            b += 1
print(*ans)

초기 방법은 for문 세 개를 만들어 진행하였으나, 시간 초과가 발생했따.
따라서, 투 포인터 알고리즘을 채택했고,
b, c라는 포인터를 만들어 각각 i+1 부터 n까지의 범위 중 가장 작은 값, 큰 값을 가르키게 설정했다.
python 3 로 채점할 시 시간초과가 발생하지만, pypy로는 문제가 없었다.

[2] 백준 14719

H, W = map(int, input().split())
arr = list(map(int,input().split()))
left, right = 0, W-1	# 투 포인터 생성
ans = 0
left_max, right_max = arr[left], arr[right]
while left < right:
    left_max = max(arr[left], left_max)
    right_max = max(arr[right], right_max)
    if left_max <= right_max:
        ans += left_max - arr[left]
        left += 1
    else:
        ans += right_max - arr[right]
        right -= 1
print(ans)

배열의 처음과 끝 인덱스를 포인터로 설정하고 각각 왼쪽, 오른쪽 최댓값 변수를 만들었다.
while문을 돌면서 각 사이드의 최댓값들을 갱신해주고 최댓값들의 크기를 비교해서 포인터를 옮겨주는 방법을 채택했다.