[이론] 투포인터(Two pointers)

투포인터

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

- 2개의 변수를 이용해 리스트 상의 위치를 기록한다.

- O(n)

- case) 문제에서 연속된 데이터 구간을 처리할 때, 배열의 특정 연속된 구간을 처리할 때

 

 

* 특정한 합을 가지는 부분 연속 수열 찾기

- 시작점을 오른쪽으로 이동시키면 합이 감소하고, 끝점을 오른쪽으로 이동시키면 합 증가한다

- 음수데이터가 있으면 투포인터 불가하다

EX ) 1 2 3 2 5에서 부분합이 5가 된는 부분연속 수열의 개수 찾기 ( 1 2 3 2 5 / 1 2 3 2 5 / 1 2 3 2 5) 

1. 시작점과 끝점이 첫번째 원소의 인덱시를 가리키도록 한다 2. 현재 부분합이 M과 같다면 카운트한다 3. 현재 부분합이 M보다 작으면 end를 1증가시킨다 4. 현재부분합이 M보다 크거나 같으면 START를 1증가 킨다  5. 모든 경우를 확인할 때까지 2번 반복

#특정한 합을 가지는 부분 연속 수열 찾기
#
import sys
n=5 #데이터의 개수
m=5 #찾고자 하는 부분합
data=[1,2,3,2,5]

cnt=0
interval_sum=0
end=0

for start in range(n):

    while interval_sum < m and end < n : #부분합이 5보다 작으면
        interval_sum += data[end]
        end+=1

    #부분합이 m일때
    if interval_sum == m:
        cnt+=1

    interval_sum -= data[start]

print(cnt)

 

*정렬되어 있는 두 리스트의 합집합 

- 정렬된 리스트 A와 B의 데이터 개수가 n,m이라고 할 때, O(N+M)

EX) [1,3,5] [2,4,6,8] 

1. 정렬된 리스트 A와 B를 입력받는다 2. 리스트 A에서 처리되지 않은 원소 중 가장 작은 원소를 i가 가리키도록 한다 3. 리스트 B에서 처리되지 않은 원소 중 가장 작은 원소를 j가 가리키도록 한다 4. A[i] 와 B[j] 중에서 더 작은 원소를 결과 리스트에 담는다 5. A와 B에서 더 이상 처리할 원소가 없을 때까지 2~4 반복

# 정렬되어 있는 두 리스트의 합집합
#
import sys
n,m=3,4
a=[1,3,5]
b=[2,4,6,8]

result=[0]*(n+m)
i,j,k=0,0,0
#모든 원소가 결과 리스트에 담길 때까지 반복
while i<n or j<m:
    #B의 원소가 모두 처리 되었거나, A의 원소가 더 작을 때
    if j>=m or (i<n and a[i] <= b[j]):
        #리스트 a의 원소를 결과 리스트로 옮기기
        result[k]=a[i]
        i+=1
    #A의 원소가 모두 처리 되었거나, B의 원소가 더 작을 때
    else:
        result[k]=b[j]
        j+=1
    k+=1
for i in result:
    print(i,end=' ')