[python]투 포인터

들어가며

이글은 동빈나님의 이코테 강의를 보며 정리한 글입니다.

투 포인터

투 포인터는 배열을 순차적으로 접근할 때, 두 개의 포인터의 위치를 기록해나가며 처리하는 알고리즘을 의미합니다. 주로, 배열에서의 연속적인 구간에 대한 요구사항이 있을 경우 사용하게 됩니다.

아래와 같은 배열이 있다고 하겠습니다.

이 배열에서 만약 합이 $M$인 구간의 개수를 구해야 한다면 어떻게 할 수 있을까요?
기존에 누적합을 이용하여 순회한다면 누적합 배열을 생성하여 누적합 배열을 순회하며 누적합이 $M$인 모든 구간을 순회할 것입니다.

하지만 이렇게 누적합을 순회하게 되면 결국 이중반복을 이용하기 때문에 시간복잡도가 $O(N^2)$이 소요되게 될 것입니다.

이러한 경우 투 포인터를 이용하게 되면 빠르게 원하는 답을 구할 수 있게 됩니다. 투 포인터는 좌 우 포인터를 생성하여 인덱스를 가르키게 하고, 아래와 같은 규칙을 통해서 포인터의 값을 갱신하게 됩니다. 이 규칙은 문제의 요구사항에 따라서 각기 다를 수 있습니다.

1. 좌 우 포인터가 가르키는 인덱스를 기반으로 한 구간합을 구한다.
2. 구간합이 기준값보다 작다면 좌 포인터를 1 증가시킨다.
3. 구간합이 기준값보다 크거나 같다면 우 포인터를 1 증가시킨다.
4. 좌 우 포인터가 역전되거나 우 포인터가 배열의 크기를 넘는다면 순회를 종료한다.

이제, $M=15$라는 가정하에 투 포인터 알고리즘을 수행해보도록 하겠습니다.

가장 먼저 두개의 포인터를 지정합니다. 두개의 포인터의 위치는 문제의 요구사항에 따라 다를 수 있지만, 여기서는 모두 0번 인덱스로 지정한 상태라고 하겠습니다.

푸른색은 좌 포인터, 붉은색은 우 포인터라고 하겠습니다. 이 포인터들이 가르키는 인덱스를 기준으로 배열에서의 구간합을 구해줍니다. 여기서는 누적합을 사용해도 무방합니다. 지금은 두개의 포인터 모두 0번 인덱스를 가르키고 있으니 0입니다.(누적합 사용)

0은 문제에서 요구하는 15보다 작으므로 우 포인터를 1증가시키고 다시 구간합을 구해줍니다.

이제는 10이 구간합입니다. 마찬가지로 10은 15보다 작습니다. 우 포인터를 다시 1 증가시키고 다시 이전과정을 반복하겠습니다.

이제는 구간합이 12가 되었습니다. 마찬가지로 우 포인터가 증가합니다.

지금은 구간합이 43이 되었습니다. 이제는 좌 포인터가 증가하여 구간합을 줄이게 됩니다.

이렇게, 좌 우 포인터를 규칙에 따라서 갱신하며 구간합을 구하고 기준값과 비교하는 연산을 반복하여 기준값과 같은 구간을 찾게 됩니다.

이러한 과정을 반복하며 15인 구간을 찾게 됩니다. 위 상황에서는 11과 4가 연속하는 상황에서만 15가 나오게 됩니다.

이를 코드로 구현하면 아래와 같습니다.

x = 15
arr = [10, 2, 31, 6, 2, 11, 4, 21]
pSum = [0 for _ in range(9)]
# 누적합 배열 구하기
for i in range(1, 8):
    pSum[i] = pSum[i - 1] + arr[i - 1]

ans = 0
left, right = 0, 0
# 투 포인터 알고리즘 수행
while left <= right and right < 9:
	# 구간합 연산
    total = pSum[right] - pSum[left]
    # 조건과 같으면 카운트
    if total == x:
        ans += 1
    # 조건보다 작다면 우 포인터 증가
    if total < x: right += 1
    # 조건보다 크거나 같으면 좌 포인터 증가
    else: left += 1
print(ans)