★Two-Pointers Upper-Intermediate I - 6 Solved★

★ 3273 두 수의 합 ★

 

import sys
input=sys.stdin.readline
n=int(input())
l=list(map(int,input().split()))
X=int(input())

#array
l.sort()

#two-pointers
x,y=0,n-1
ans=0

while x<y:
    total=l[x]+l[y]
    if total == X:
        ans+=1
        x+=1
        y-=1
    elif total < X:
        x+=1
    else: #total > X
        y-=1
        
print(ans)

 

🍡 오름차순 정렬 뒤, x를 배열 왼쪽 끝 / y를 배열 오른쪽 끝에 배치. l[x]+l[y]가 X보다 클 경우, x를 아무리 오른쪽으로 이동해도 X보다 클 수 밖에 없음. 따라서 y를 왼쪽으로 이동 / l[x]+l[y]가 X라면 정답 찾음! ans+=1 한 뒤, l[x]와 l[y]는 이제 X 나오는 연산에 필요 없으므로 x 오른쪽 이동, y 왼쪽 이동 / l[x]+l[y]가 X보다 작다면 y를 아무리 왼쪽으로 이동해도 더 작아지기에 X를 만들수 없음. 따라서 x를 오른쪽으로 이동. 이 때 아래 그림과 같이 x가 5이고 y가 9일 때, 이미 y가 지나친 10, 11, 12는 x가 5일 때 또 점검할 필요가 없다(투 포인터 특징). X와 같거나 X보다 크다면 당연히 오른쪽 y가 지나친 원소들은 볼 필요가 없고, X보다 작다면 답의 가능성이 있을 수는 있지만, 이는 이미 y가 기존 y보다 더 클 경우 진행을 했기에 더 이상 10, 11, 12를 x가 5일 때 check할 필요 없다. 시간복잡도 O(logn+n+n)   

---

★ 2003 수들의 합 2 ★

import sys
input=sys.stdin.readline
N,M=map(int,input().split())
l=list(map(int,input().split()))

y=0
cumsum=0
ans=0
for x in range(N):
    while y<N and cumsum<M:
        cumsum+=l[y]
        y+=1
    if cumsum==M:
        ans+=1
    cumsum-=l[x]
print(ans)

 

🍡 i와 j 모두 배열 왼쪽 끝에 커서로 놓고, x 고정한 상태에서 M이 작을 때까지 y 계속 이동. 커지거나 같다면, 같을 경우 ans += 1, 그 다음 오른쪽으로 x 이동해서 현재 누적합에서 l[x] 빼기. 문제 자체에 A[i] ~ A[j] 사이의 누적합이라고 해서 투 포인터 알고리즘 사용의 정당성 증명 필요없이 바로 투 포인터 사용

---

★ 2559 수열 ★

 

import sys
input=sys.stdin.readline

N,K=map(int,input().split())
l=list(map(int,input().split()))

ans=-1_000_000_000
cursum=0
y=0
cnt=0
for x in range(N):
    while y<N and cnt<K:
        cursum+=l[y]
        cnt+=1
        y+=1
    if cnt==K:
        ans=max(ans,cursum)
        cursum-=l[x]
        cnt-=1
    else:
        break
print(ans)

 

🍡 k개의 연속한 누적합이므로 투 포인터 사용의 정당성은 자명. cnt<K일 때까지 y+=1하며 더해나가고, cnt==K라면 ans update(최대라면)와 함께 cursum 누적합에 l[x] 빼고, cnt-=1. 만약 y가 배열 끝으로 이동해서 cnt==K아니라면 더 이상 연속해서 누적합을 구할 수 없으므로 종료

---

★ 1940 주몽 ★

 

import sys
input=sys.stdin.readline

N=int(input())
M=int(input())
l=list(map(int,input().split()))
l.sort()
x,y=0,N-1
cumsum=200_001
ans=0

while x<y:
    total=(l[x]+l[y])
    if total < M:
        x+=1
    elif total == M:
        ans+=1
        x+=1
        y-=1
    else: #total > M
        y-=1
print(ans)

 

🍡 3273 두 수의 합과 동일 유형(투 포인터 안써도 되나 투 포인터로 O(N)) 풀이)

---

★ 2531 회전 초밥 ★

 

🍡 G4 15961 회전 초밥 풀이 참조(N 조건 범위가 더 커짐)

---

★ 6159 Costume Party ★

import sys
input=sys.stdin.readline
N,S=map(int,input().split())
cows=[int(input()) for _ in range(N)]
cows.sort()
i,j=0,len(cows)-1
ans=0
while i<j:
    total=cows[i]+cows[j]
    if total > S:
        j-=1
    else:
        ans+=(j-i)
        i+=1
print(ans)

 

🍡 pair 구성 내용의 합이 S보다 큰 pair의 개수를 구하는 문제. 직접 n^2으로 돌려도 되지만 정렬 뒤, 투 포인터로(O(nlogn+n)) 찾을 수 있다. 양 포인터를 처음과 끝에 두고, 현재 total이 S보다 크다면 j-=1. 그렇지 않다면 j-i를 pair 수로 누적 업데이트. 그리고 i+=1

---