[투 포인터] 자료구조
1. 개념
투 포인터 : 2개의 포인터
파이썬에서는 리스트를 생성하고 리스트 index를 이용해서 포인터를 지정하면 된다.
* 시간복잡도를 줄일 때 사용하기 좋다.
어떤 애들을 포인터로 지정하면 될까?
대표적인 경우 두 가지를 소개해보자면
(1) 속도가 다른 투포인터 -> slow runner, fast runner
(2) 시작점과 끝점에서 출발해서 가운데에서 만나는 투포인터
[1] 속도가 다른 투포인터 : slow runner, fast runner
i : slow runner
j : fast runner
[2] 시작점과 끝점에서 출발해서 가운데에서 만나는 투포인터
2. 문제 풀이
# 1 수들의 합5 - 백준 2018번
https://www.acmicpc.net/problem/2018
2018번: 수들의 합 5
어떠한 자연수 N은, 몇 개의 연속된 자연수의 합으로 나타낼 수 있다. 당신은 어떤 자연수 N(1 ≤ N ≤ 10,000,000)에 대해서, 이 N을 몇 개의 연속된 자연수의 합으로 나타내는 가지수를 알고 싶어한
www.acmicpc.net
* 속도가 다른 투포인터
# n 입력 받기
n = int(input())
start = 1
end = 1
sum = 1
cnt = 1 # start = end = n 인 경우 미리 포함
while end != n:
# cnt 1 증가 / s 한 칸 옮기기
if sum == n:
cnt += 1
sum -= start
start += 1
# e 한 칸 옮기기
elif sum < n:
end += 1
sum += end
# s 한 칸 옮기기
else:
sum -= start
start += 1
print(cnt)
# 2 주몽 - 백준 1940번
https://www.acmicpc.net/problem/1940
1940번: 주몽
첫째 줄에는 재료의 개수 N(1 ≤ N ≤ 15,000)이 주어진다. 그리고 두 번째 줄에는 갑옷을 만드는데 필요한 수 M(1 ≤ M ≤ 10,000,000) 주어진다. 그리고 마지막으로 셋째 줄에는 N개의 재료들이 가진 고
www.acmicpc.net
* 시작점과 끝점에서 출발해서 가운데에서 만나는 투포인터
# n,m / 갑옷 재료 입력받기
n = int(input())
m = int(input())
num = list(map(int,input().split()))
# num 정렬
num.sort()
a = 0
b = len(num)-1
cnt = 0
i = num[a]
j = num[b]
while i < j:
if i + j < m:
a += 1 # i 한 칸 옮기기
i = num[a]
elif i + j == m:
a += 1 # i 한 칸 옮기기
i = num[a]
cnt += 1 # cnt 1 증가
else:
b -= 1 # j 한 칸 옮기기
j = num[b]
print(cnt)
# 3 '좋은 수' 구하기 - 백준 1253번
https://www.acmicpc.net/problem/1253
1253번: 좋다
첫째 줄에는 수의 개수 N(1 ≤ N ≤ 2,000), 두 번째 줄에는 i번째 수를 나타내는 Ai가 N개 주어진다. (|Ai| ≤ 1,000,000,000, Ai는 정수)
www.acmicpc.net
n = int(input())
numlist = list(map(int,input().split()))
numlist.sort()
good = 0
for a in range(n):
target = numlist[a]
i = 0
j = n-1
while i < j:
if numlist[i] + numlist[j] == target:
if i != a and j != a:
good += 1
break
elif i == a:
i += 1
else:
j -= 1
elif numlist[i] + numlist[j] < target:
i += 1
else:
j -= 1
print(good)