[Python] 4. 투 포인터

1. 투 포인터 

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

예를 들어, 한 반에 40명의 학생이 있을 때, 모든 학생을 번호 순서대로 일렬로 세운 뒤, 학생들을 순차적으로 지목해야 할 경우를 생각해보자. 2, 3, 4, 5, 6, 7번 학생을 지목할 때, 번호로 한명씩 부르기보다는 '2번부터 7번까지의 학생'이라고 부를 수 있다. 이처럼 순차적으로 접근해야 할 때는 '시작점'과 '끝점' 2개의 점으로 접근할 데이터의 범위를 표현할 수 있다. 

특정한 합을 가지는 부분 연속 수열 찾기 문제를 풀어보자. 양의 정수로만 구성된 리스트가 주어졌을 때, 그 부분 연속 수열 중에서 '특정한 합'을 갖는 수열의 개수를 출력하는 문제이다. 특정한 부분합을 M이라고 할때 풀이 순서는 다음과 같다. 

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

n = 5 # 데이터의 개수 N
m = 5 # 찾고자 하는 부분합 M
data = [1, 2, 3, 2, 5] # 전체 수열

count = 0
interval_sum = 0
end = 0

# start를 차례대로 증가시키며 반복
for start in range(n):
    while interval_sum < m and end < n: # end를 가능한 만큼 이동시키기
        interval_sum += data[end]
        end += 1
    # 부분합이 m일 때 카운트 증가
    if interval_sum == m:
        count += 1
    interval_sum -= data[start]

print(count)
# 3

투 포인터 알고리즘을 코드로 구현한 것은 위와 같다. 결과적으로 카운트된 경우의 수는 3이다. 따라서 부분합이 5가 되는 부분 연속 수열의 개수는 3개인 것을 알 수 있다. 

이 문제를 투 포인터 알고리즘으로 해결할 수 있는 이유는 기본적으로 시작점을 오른쪽으로 이동시키면 항상 합이 감소하고, 끝점을 오른쪽으로 이동시키면 항상 합이 증가하기 때문이다. 만약 리스트 내 원소에 음수 데이터가 포함되어 있는 경우에는 투 포인터 알고리즘으로 문제를 해결할 수 없다. 

이 밖에도 투 포인터 알고리즘은 '정렬되어 있는 두 리스트의 합집합'과 같은 문제에 효과적으로 사용할 수 있다. 두 리스트의 모든 원소를 합쳐서 정렬한 결과를 계산하는 것이 문제의 요구사항이다. 

이 문제를 풀기 위해서는 2개의 리스트 A, B가 주어졌을 때, 2개의 포인터를 이용하여 각 리스트에서 처리되지 않은 원소 중 가장 작은 원소를 가리키면 된다. 이 문제에서는 기본적으로 이미 정렬된 결과가 주어지므로 리스트 A와 B의 원소를 앞에서부터 확인하면 된다. 

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

# 사전에 정렬된 리스트 A와 B 선언
n, m = 3, 4
a = [1, 3, 5]
b = [2, 4, 6, 8]

# 리스트 A와 B의 모든 원소를 담을 수 있는 크기의 결과 리스트 초기화
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]): # 리스트 B의 모든 원소가 처리되었거나, 리스트 A의 원소가 더 작을 때
        result[k] = a[i] # 리스트 A의 원소 결과 리스트로 옮기기
        i += 1
    # 리스트 A의 모든 원소가 처리되었거나, 리스트 B의 원소가 더 작을 때
    else:
        result[k] = b[j] # 리스트 B의 원소를 결과 리스트로 옮기기
        j += 1
    k += 1

# 결과 리스트 출력
for i in result:
    print(i, end=' ')
    
# 1 2 3 4 5 6 8

 

결과적으로 정렬된 리스트 A와 B의 데이터 개수가 각각 N, M이라고 할 때, 이 알고리즘의 시간 복잡도는 O(N + M)이 된다. 단순히, 각 리스트의 모든 원소를 한 번씩만 순회하면 되기 때문이다. 

 

 

 

'이것이 코딩테스트다'를 읽고 공부한 내용을 바탕으로 작성하였습니다.