[파이썬] 투 포인터

Contents

문제

내용

• 수열 내에서 부분합 계산하는 문제

• 수열에 입력되는 요소의 개수는 100만 개, 부분합의 최댓값은 10억

• 알고리즘으로 직관적으로 풀면 100만 * 100만 = 약 10조? 회 연산이 발생하여 반드시 시간 초과가 발생한다. 그러므로, 실행시간이 더 빠른 알고리즘을 적용하여 풀어야 한다.

• 투 포인터 알고리즘을 사용하면 이 걸린다. 투 포인터 알고리즘은 부분합 구하기에 적합한 알고리즘이기도 하다.

투 포인터 알고리즘

1. 배열 순회는 왼쪽을 기준으로 한다.

def two_pointer_search(arr):
	partial_sum = 0

	for left in range(len(arr)):

1. 오른쪽 포인터는 left 반복문의 안쪽에 반복문으로 둔다. 오른쪽 포인터에 대해서는 두 가지 조건문을 두고 반복하며 한 칸씩 옮긴다. 두 조건문을 모두 충족해야 반복문을 수행하게 해야 한다.
1. 오른쪽 포인터가 배열의 인덱스 끝에 도달하지 않았는가?
2. 부분합이 목표하고자 하는 최대값에 도달하지 않았는가?

def two_pointer_search(arr, target_sum):
	partial_sum = 0

	for left in range(len(arr)):
		while right < len(arr) and partial_sum < target_sum:
			right += 1 

 

2. 조건문에 따라 오른쪽 포인터가 이동한 상태다. 계산한 부분합에 대해 필요한 작업을 한 후, 왼쪽 포인터를 한 칸 옮긴다.
• left를 한 칸 옮기기 전에, 현재 left가 가리키는 값을 부분합에서 빼야 한다. 부분합은 두 포인터 지점 사이의 합이기 때문이다.

def two_pointer_search(arr, target_sum):
	partial_sum = 0

	for left in range(len(arr)):
		while right < len(arr) and partial_sum < target_sum:
			right += 1

	# Do something

	partial_sum -= left # 왼쪽 포인터의 값을 부분합에서 제거
	# 왼쪽 포인터는 for문에 의해 1씩 업데이트

1. 왼쪽 포인터가 배열 끝에 도착할 때까지, 1~3 과정을 반복한다.

문제 풀이 코드

def solution(sequence, k):    
    result = []
    partial_sum = 0
    right = 0

    for left in range(len(sequence)):        
        while right < len(sequence) and partial_sum < k:
            partial_sum += sequence[right]
            right += 1
        
        if partial_sum == k:
            if result == []:
                result = [left, right - 1]
            else:
                if result[-1] - result[0] > (right - 1) - left:
                    result = [left, right - 1] 
                    
        partial_sum -= sequence[left]   # left가 옆 칸으로 이동하기 전에 현재 칸을 빼야 한다.
    
    return result

투포인터 풀이 팁

• 왼쪽, 오른쪽 포인터 모두 순방향으로만 이동하고 절대 후퇴하지 않는다.

• 만약 left가 하나 올라갈 때마다, right가 left 지점으로 다시 후퇴한다면 이때 시간복잡도는 O(n^2)가 된다. 이렇게 되면 투포인터를 쓰는 의미가 없다.

적용 결과

출처