투 포인터 (2021/02/16)

투 포인터란 2개의 변수를 이용해 리스트 상의 위치를 기록하는 것이다.

 

부분 합

 

리스트 [1, 2, 3, 2, 5] 가 주어질 때, 부분 합이 5인경우는 [2, 3], [3, 2], [5] 세 경우이다.

 

구하는 방법은

 

1. s와 e를 이용해서 0번째 자리부터 탐색한다.

2. 부분합이 5보다 작으면 e+1

3. 부분합이 5보다 크거나 같으면 s+1

4. 부분합이 5일 때, count 1 증가

 

n=5
m=5
data=[1,2,3,2,5]
count=0
interval_sum=0
end=0

for s in range(n):
    while interval_sum<m and end<n:
        interval_sum+=data[end]
        end+=1
    if interval_sum ==m:
        count+=1
    interval_sum-=data[s]
print(count)

 

포인터를 이용한 정렬

 

a = [1, 3, 5]

b = [2, 4, 6, 8] 일 때,

 

포인터를 이용하여 정렬할 수 있다.

 

1. i값과 j값을 비교한다.

2. 둘 중 작은 값을 비어있는 리스트에 넣는다.

3. 비어있는 리스트의 주소값을 증가시킨다.

 

n=3
m=4
a=[1,3,5]
b=[2,4,6,8]
result=[0]*(n+m)
i=0
j=0
k=0
while i<n or j<m:
    if j>=m or(i<n and a[i] <= b[j]):
        result[k]=a[i]
        i+=1
    else:
        result[k]=b[j]
        j+=1
    k+=1
    
for i in result:
    print(i, end=' ')