투포인터 알고리즘

투 포인터(Two Pointers)란 리스트에 순차적으로 접근 할 때 두개의 포인터를 이용해서 처리하는 알고리즘이다

투 포인터를 이용한 문제는 리스트에서 특정 합을 찾거나 특정 부분합을 찾을 때 이용할 수 있다

 

 

---

만약 리스트가 주어지고 그 리스트에 특정합이 되는 수열을 찾으라는 문제가 있으면 두개의 포인터를 이용해서 해결 가능하다

target = 11일때 리스트 크기 11인 경우

방법

1. 시작위치에서 부분합을 구하고 그 부분합이 target 보다 작으면 end(파란색)을 한칸 이동시키고 이동시킨 곳의 값을 더해 부분합을 구한다
2. 부분합이 target 보다 크면 start(주황)을 한칸 이동시키고 부분합에서 포인터가 이동하기 전 값을 뺀다
3. 부분합이 target과 같다면 그 수열을 문제에 따라 처리한다

큰 방법으로는 위 3가지 이지만 세세하게 따지면 생각해야 될 경우의 수가 많다

---

end가 리스트의 최대 위치에 있는 경우 end는 더 이상 증가 할 수 없다 만약 이 경우에 부분합이 target 보다 작다면 start를 키워봤자 -만 해야 하므로 break로 끝내는게 효율적이다

 

또 start == end 인경우 부분합이 target보다 크다면 start를 증가시켜야 하는데 이런 경우 start > end 가 되기 때문에 예외적으로 end를 증가시켜야 한다 end가 최대라면 당연히 break로 종료

#s == target인 경우 min_list에 추가하도록 만든 코드
#파이썬
import sys
from collections import deque
input = sys.stdin.readline


n,target = map(int,input().split())
array = deque(map(int,input().split()))
array.appendleft(0)

min_list = []
start = 1
end = 1
s = array[start]

while start <= end:
    #start와 end 계산후에 s를 구한다
    if s == target:
        min_list.append([start,end])

        if end == n:
            break
        else:
            end = end + 1
            s = s +array[end]

    elif s < target:
        if end == n:
            break
        else:
            end = end + 1
            s = s + array[end]
                   
    else: #s > target
        
        if start == end:
            if end == n:
                break
            else:
                end = end + 1
                s = s + array[end]
        else:
            s = s - array[start]
            start = start + 1


if len(min_list) == 0:
    print(0)
else:
    print(min_list)

---

결과

11 11

3 1 2 5 4 7 10 11 9 6 8

[[1, 4], [3, 5], [5, 6], [8, 8]]