[Python] 투 포인터

투 포인터

리스트에서 순차적으로 접근하려고 할 때 두 개의 포인터를 사용하여 원하는 값을 찾거나 구간 합, 반복 등의 처리를 할 때 유용한 알고리즘

• 시작점(start)와 끝점(end) 2개의 점으로 접근할 데이터의 범위 표현 가능
• 슬라이딩 윈도우와 유사한 알고리즘이지만, 투 포인터는 가변적인 구간을 탐색할 수 있음
• 정렬되어있는 두 리스트의 합집합을 구할 때도 사용할 수 있음
• 리스트 정렬이 선행되어야 하며, 양방향 포인터 이동
• 전체 탐색(반복문)은 O(N^2), 투 포인터를 사용하면 O(N)

빈출 예제 : 특정한 합을 가지는 부분 연속 수열 찾기

1. 리스트 입력 받기
   2-1. 시작점(start) = 0, 끝점(end) = n-1로 초기화
   2-2. 시작점(start), 끝점(end)을 0으로 초기화
2. 현재 부분 합이 target과 같다면 count += 1
3. 현재 부분 합이 target 보다 크거나 같은 경우 start + 1
   5-1. 현재 부분 합이 target 보다 작은 경우 end - 1 // 2-1번의 경우
   5-2. 현재 부분 합이 target 보다 작은 경우 end + 1 // 2-2번의 경우
4. 모든 경우를 확인할 때 까지 3 ~ 5번 과정을 반복

예제 코드 1 : N-1 Root

array.sort() # 오름차순 정렬
start, end = 0, n-1

while start<end:
  	Sum = array[start] + array[end]
  	if Sum > target:
			start += 1
      elif Sum < target:
      	end -= 1
      else:
      	count += 1
          start += 1
          end -= 1

예제 코드 2 : N-2 Root

n = 5 # 데이터의 개수 N
m = 5 # 찾고자하는 부분합 M
 
count = 0
interval_sum = 0
end = 0
 
# start를 차례대로 증가시키며 반복
for start in range(n):
    # end만큼 이동시키기
    while interval_sum < m and end < n:
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]
 
print(count)