투 포인터
리스트에 순차적으로 접근할 때, start 와 end 두 개의 포인터를 조작하여 접근할 데이터를 조작할 수 있다.
투 포인터가 활용되는 대표적인 문제로는 "두 수를 더해서 목표값 찾기"와 데이터의 범위(윈도우)를 표현하는 "특정한 합을 가지는 연속된 수열 찾기" 문제가 있다.
- 두 수를 더해서 목표값 찾기
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
arr = [1, 2, 3, 4, 5, 6, 7]
start = 0
end = len(arr) - 1
target = 9
while start < end:
if arr[start] + arr[end] < target:
start += 1
elif arr[start] + arr[end] > target:
end -= 1
else:
print(arr[start], arr[end])
start += 1
|
cs |
출력:
2 7
3 6
4 5
- 특정한 합을 가지는 연속된 수열 찾기 (이것이 코딩테스트다 476p)
[10, 20, 30, 20, 50]이 주어졌을 때 합이 50이 되는 배열들을 알고 싶다.
알고리즘:
부분합이 target 과 같으면 count 를 1증가시킨다.
부분합이 target 보다 작으면 end 를 1증가시킨다.
부분합이 target 보다 크거나 같으면 start 를 1증가시킨다.
핵심: start 가 오른쪽으로 한 칸 이동하면 합이 감소하고, end 가 이동하면 합이 증가한다.
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
|
arr = [10, 20, 30, 20, 50]
n = 5
target = 50
count = 0
tot = 0
end = 0
def window(s, e):
for i in range(s, e):
print(arr[i], end=' ')
print()
for start in range(n):
while end < n and tot < target:
tot += arr[end]
window(start, end)
end += 1
# 부분합이 target 충족
if tot == target:
count += 1
# tot > target, tot == target -> start += 1
window(start, end)
tot -= arr[start]
|
cs |
출력:
10
10 20
10 20 30
20 30 COUNT + 1
30
30 20 COUNT + 1
20
20 50
50 COUNT + 1
COUNT = 3
이 문제의 start 의 이동은 for start in range(n) 으로 이루어진다.