연속된 부분 수열의 합 (투 포인터 기법 사용)

주어진 배열에서 연속된 부분 수열의 합이 m이 되는 경우의 수를 구해야 할 때....

 

브루트 포스(완전 탐색) 방식을 이용한다면 O(n³)의 시간 복잡도로 시간이 초과될 가능성이 있다.

# 브루트 포스 - 시간 초과

for x in range(n):
    for y in range(x, n): 
        sum = 0  
        for i in range(x, y+1):  
            sum += a[i]
        if sum == m:	# 합이 m이면 경우의 수 증가
            cnt += 1

 

반면 투 포인터 방식을 이용한다면 O(n)의 시간 복잡도로 효율적이고 빠르게 답을 구할 수 있다.

lt = 0  # 왼쪽 포인터 (부분 수열의 시작점)
rt = 1  # 오른쪽 포인터 (부분 수열의 끝 다음 위치)
tot = a[0]  # 현재 부분 수열의 합 (초기값: 첫 번째 요소)

 

조건1: tot<m -> rt+=1

현재 부분 수열의 합이 m보다 작다면, 오른쪽 포인터(rt)를 확장하여 합을 늘린다.

(단, rt가 배열 크기 n을 넘으면 종료)

if tot < m:
    if rt < n:		# rt가 배열 끝을 넘지 않는다면
        tot += a[rt]	# 새로운 요소를 추가
        rt += 1  	# 오른쪽 포인터 이동
    else:
        break  		# 더 이상 확장할 수 없으므로 종료

 

조건2: tot==m -> lt+=1

현재 부분 수열의 합이 m과 같다면, 경우의 수(cnt)를 증가시키고 lt를 오른쪽으로 이동한다.

(중복을 방지하고 새로운 부분 수열을 찾기 위해서)

elif tot == m:
    cnt += 1  		# m을 만족하는 경우 발견 → 카운트 증가
    tot -= a[lt]  	# lt가 가리키는 값을 빼줌 (부분 수열을 줄이기 위해)
    lt += 1  		# 왼쪽 포인터 이동

 

조건3: tot>m -> lt+=1

현재 부분합이 m보다 크다면, lt를 오른쪽으로 이동하여 합을 줄인다.

else:
    tot -= a[lt]  	# 부분합이 m보다 크므로, lt를 이동해 줄이기
    lt += 1

 

마지막으로 tot이 m보다 작으면서 rt==n인 경우 break로 while문을 종료시킨다는 점을 기억하자