나동빈님의 "이것이 취업을 위한 코딩테스트다" 의 기타 알고리즘 - 투포인터를 보고 정리했습니다.

투포인터란?

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

예제

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

문제

양의 정수로만 구성된 리스트가 주어졌을 때, 부분 연속 수열 중 "특정 합"을 갖는 수열의 개수 출력하기

풀이

부분 연속 수열의 시작-끝점 기록하기

부분합을 M이라고 했을때,

1. 시작, 끝점이 첫번째 인덱스를 가리키도록
2. 현재 부분합이 M과 같은지? → 같으면 count += 1
3. 현재 부분합이 M보다 작으면 end += 1
4. 현재 부분합이 M보다 크거나 같으면 start += 1
5. 모든 원소 볼때까지 2-4 반복

코드

n = 5 #데이터의 개수
m = 5 #특정 부분 합
data = [1, 2, 3, 2, 5]

count = 0
interval_sum = 0
end = 0

#start를 차례로 증가시켜나가기
for start in range(n):
    #end를 가능한 만큼 이동
    while interval_sum < m and end < n:
        end += 1
    #부분합과 같아지면
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]
print(coount)

→ 리스트내에 양수만 존재함이 보장됨으로 사용할 수 있는 방법

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

문제

이미 정렬된 두개의 리스트가 입력으로 주어질때, 두 리스트의 모든 원소를 합쳐서 정렬한 결과 반환

풀이

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

코드

n, m = 3, 4
a = [1, 3, 5]
b = [2, 4, 6, 8]

#리스트 A와 B의 모든 원소를 담을 수 있는 리스트 초기화
result = [0]*(n+m)
i, j, k = 0

while i<n and j<m:
    #B가 전부 처리되었거나 A의 원소가 더 작을 때
    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

print(result)

→ 머지소트와 같은 일부 알고리즘에 사용됨