Two pointer

• 투포인터 기법은 List에서 임의의 부분 List를 추출하여 분석하기 위한 알고리즘
• Two pointer 를 활용하면 O(N^2)의 알고리즘을 O(N)으로 줄일 수 있음
• 대표적인 예시는 특정 list에서 부분합을 만족하는 sub list 존재 여부 판정 혹은, 2개의 List 비교하는 문제에서 많이 활용 된다.

1개의 List에서 활용 방안

BOJ 2003

• N개의 길이인 수열 A[1], A[2] ... A[N] 이 있을때, i번째 부터 j번째 수까지 합이 M이 되는 경우를 찾는 문제

  투포인터를 알고리즘을 짜기 전에 사전 조건

  • 투 포인터는 각 start와 End라고 정의
  • 리스트 탐색은 start값이 배열의 길이 N 과 똑같아 지면 멈춘다.
  • 투 포인터 모두 리스트의 시작지점 인덱스 0 으로 초기값으로 가진다.
  • 리스트의 부분합이 5보다 작다면 End + 1 을 계산해준다. End 값이 리스트의 마지막 인덱스의 값이 똑같게 된다면 Start + 1을 해준다.
  • 리스트의 부분합이 5보다 같거나 작으면 Start + 1을 계산해주고, 만약 부분합이 5가 된다면 결과값에 +1을 한다.

• start = 1 , end = 2 일때 리스트의 부분합이 5이기 때문에 결과값을 카운트 해준다.

• 이러한 과정을 계속하다가 END값이 마지막 인덱스를 가리키게 되면 STart 값을 증가 시켜준다.

소스코드 구현

import sys

lst_length, Test_sum = list(map(int,sys.stdin.readline().split(" ")))
lst_input = list(map(int,list(sys.stdin.readline().split(" "))))

result = 0
start = 0
end = 0
lst_sum = lst_input[0]

# 투포인터 기법으로 end와 start 둘다 사용함

while(start <= lst_length-1):
    if lst_sum == Test_sum:
        result += 1

    if lst_sum > Test_sum:
        lst_sum -= lst_input[start]
        start += 1
    elif lst_sum <= Test_sum:
        if end < lst_length-1:
            lst_sum += lst_input[end+1]
            end += 1
        else:
            lst_sum -= lst_input[start]
            start += 1
  
print(result)