투포인터 알고리즘 Two Pointers algorithm (파이썬)

투포인터 알고리즘

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

ex) 주문서 10개 중 1번부터 3번 주문서 총액을 계산할 때 시작점은 1번 주문서, 끝 점은 3번 주문서가 된다.

 

주어진 리스트 중 특정한 합을 가지는 수열 찾기

 

현재 주어진 리스트= [1,2,4,6,8] 에서 합이 6인 수열의 개수 찾기

count, start와 end는 0 부터 시작한다. 

만약 start부터 end까지 수열의 합이 6을 넘지 않는다면 end를 1 증가시킨다.

start부터 end까지 수열의 합이 6을 넘었다면 합에서 start 번째 수를 뺀뒤, start를 1증가시킨다.

 수열의 합이 6이라면 count를 1 증가시킨다.

 

이 과정을 end가 리스트 끝에 도달할때 까지 반복한다.

 

python(파이썬) 코드

s=6
arr=[1,2,4,6,8]
n=len(arr)+1
start,end=0,0
count=0
com=0 #수열의 합

while True:
    if com>=s:    
        count+=1
        com-=arr[start]       
        start+=1
    
    elif end==n:
        break
    else:
        com+=arr[end]
        end+=1
    

print(count)