투 포인터 (two pointer) 기법

투 포인터로 특정한 합을 가지는 부분 연속 수열 찾기

투 포인터 기법이란 리스트에 순차적으로 접근해야 할 때 두 개의 점을 이용해 위치를 기록하면서 처리하는 기법이다. 이 문제는 O(N) 의 시간복잡도로 해결할 수 있다. (O(N)는 선형시간 알고리즘이다.)

 

 

문제

아래와 같이 자연수로 구성된 N개의 수열이 있다. 합이 M인 부분 수열의 개수를 구하시오.

1

2

3

2

5

원리

 

1. 시작점(start), 끝점(end)이 첫 번째 원소의 인덱스(0)를 가리키도록 한다.

2. 현재 부분 합이 M과 같다면 카운트를 증가시킨다.

3. 현재 부분 합이 M보다 작거나 같다면 end를 1 증가시킨다.

4. 현재 부분 합이 M보다 크다면, start를 1 증가시킨다.

5. 모든 경우를 확인할 때까지 2번부터 4번까지의 과정을 반복한다.

 

합 : 1 -> M이 5라고 가정했을때 현재 합이 M보다 작으므로 다음 단계에 end를 증가시킨다.

start
1	2	3	2	5
end

 

 

합 : 3 -> 합이 5보다 작으므로 또 다음 단계에 end를 증가시킨다.

start
1	2	3	2	5
	end

 

 

합 : 6 -> 합이 5보다 커졌으므로 다음 단계에 start를 증가시킨다.

start
1	2	3	2	5
		end

 

 

합 : 5 -> 합이 5가되었으므로 count를 증가시키고, 다른 경우를 찾아야 하기 때문에 end를 증가시킨다.

	start
1	2	3	2	5
		end

 

 

합 : 7 -> 합이 5보다 커졌으므로 다음 단계에 start를 증가시킨다.

	start
1	2	3	2	5
			end

 

 

합 : 5 -> 합이 5가되었으므로 count를 증가시키고, 다른 경우를 찾아야 하기 때문에 end를 증가시킨다.

		start
1	2	3	2	5
			end

 

 

합 : 10 -> 합이 5보다 커졌으므로 다음 단계에 start를 증가시킨다.

		start
1	2	3	2	5
				end

 

 

합 : 7 -> 합이 5보다 커졌으므로 다음 단계에 start를 증가시킨다.

			start
1	2	3	2	5
				end

 

 

합 : 5 -> 합이 5가되었으므로 count를 증가시키고, end가 배열의 끝에 왔기 때문에 종료한다.

				start
1	2	3	2	5
				end

 

 

코드

# 데이터개수 n과 부분 연속 수열의 합 m을 입력받는다.
n, m = 5, 5
data = [1, 2, 3, 2, 5]

count = 0
sum = 0
end = 0

# start를 차례대로 증가시키며 반복한다.
for start in range(n):
  # 매 start 마다 end를 가능한 만큼 오른쪽으로 이동시킨다.
  while sum < m and end < n:
    sum += data[end]
    end += 1
  
  if sum == m:
    count += 1
  
  sum -= data[start]

print(count)
  

 

 

정리

선형시간의 알고리즘 이기 때문에 시간을 단축시킬 수 있다.

배열에서의 구간 합이나 구간에 대한 정보를 처리하기 위해서 사용할 수 있는 기법이다.