★Two-Pointers Advanced I - 10 Solved★

★ 15961 회전 초밥 ★

 

import sys
input=sys.stdin.readline
from collections import defaultdict

N,d,k,c=map(int,input().split())
kinds=[int(input()) for _ in range(N)]
y,ans,cnt,freq=0,0,0,defaultdict(int)
for x in range(N):
    while cnt<k:
        if y<N:
            cnt+=1
            freq[kinds[y]]+=1
            y+=1
        elif N<=y:
            cnt+=1
            freq[kinds[(y-1)%(N-1)]]+=1
            y+=1
    cur_kinds=freq.keys()
    if c in cur_kinds:
        ans=max(ans,len(cur_kinds))
    else:
        ans=max(ans,len(cur_kinds)+1)
    freq[kinds[x]]-=1
    if freq[kinds[x]]==0:
        del freq[kinds[x]]
    cnt-=1
print(ans)

 

🧦 x와 y 투 포인터 모두 첫 초밥부터 시작하되, k개의 묶음마다 진행하므로(슬라이딩 윈도우 포스팅 참조), x가 전체 초밥 x(1)부터 x(8)까지 움직일 때 y의 끝은 y(1) 부터 y(11)까지 (k=4일 경우) 움직인다 / dictionary 활용해 freq로 종류 개수 update하며 freq.keys()로 중복 초밥 여부 검사해 c 쿠폰 사용하거나 안하거나 ans값 update (freq dictionary로 sushi 종류 알아보기 시간 단축)

---

★ 1806 부분합 ★

 

import sys
input=sys.stdin.readline
N,S=map(int,input().split())
ans=100_000
l=list(map(int,input().split()))
cum=0
y=0
length=0
for x in range(N):
    while cum<S and y<N:
        cum+=l[y]
        length+=1
        y+=1
    if cum>=S:
        ans=min(ans,length)
    cum-=l[x]
    length-=1

if ans == 100_000:
    print(0)
else:
    print(ans)

 

🧦 x와 y 두 포인터 모두 왼쪽 끝부터 시작하며, y가 오른쪽으로 이동하며 누적합이 S이상이 될때까지 진행. x가 오른쪽으로 이동시, y가 처음부터 진행할 필요 없음. 누적합이므로, 기존 x가 가리키는 원소가 빠져 S이상이 될리 없기 때문(투 포인터 알고리즘 적용). 아래 그림 참조

: x가 5일때 y가 10까지 진행되었고(S=15), x가 그다음 1로 진행될 때, y가 다시 5부터 일일이 진행할 필요 없다. 이미 부분누적합은 S이상임을 확인하였고, 여기서 5를 뺀 현재 부분누적합에서 다시 y가 처음부터 진행한다면 S이상이 될리가 없기 때문(이전 x일 때 y가 돌면서 앞의 y는 S이하임을 증명하였기에) 따라서  x와 y모두 array를 처음부터 끝까지 각각 한번만 돌기 때문에 O(N+N)

---

★ 1644 소수의 연속합 ★

 

def get_sieve(n):
    if n == 1:
        return []
    elif n == 2:
        return [2]
    elif n == 3:
        return [2,3]
    else:
        nums=[True]*(n+1)
        nums[1]=False
        end=int(n**(1/2))
        for x in range(2,end+1):
            if nums[x]: #if True
                for y in range(x,n+1,x):
                    nums[y]=False
                nums[x]=True
        return [i for i in range(2,n+1) if nums[i]]
        

N=int(input())
primality_numbers=get_sieve(N)
l=len(primality_numbers)
y=0
cursum=0
ans=0
for x in range(l):
    while y<l and cursum<N:
        cursum+=primality_numbers[y]
        y+=1
    if cursum==N:
        ans+=1
    cursum-=primality_numbers[x]
print(ans)

 

🧦 에라토스테네스 체로 N까지의 소수만 구성되어 있는 sieve를 구한 뒤, 위 1806 부분합 문제와 동일하게 부분누적합이 N이 되는 지 확인. x가 증가하는 과정에서 y가 0부터 차례대로 점검할 필요 없으므로(투 포인터) 쉽게 O(N+N)

---

★ 2470 두 용액 ★

 

import sys
input=sys.stdin.readline

N=int(input())
l=list(map(int,input().split()))
l.sort()
ans=2_000_000_001
x,y=0,(N-1)
ans_liquid=[]
while x<y:
    total=(l[x]+l[y])
    if abs(total) < ans:
        ans=abs(total) #ans update
        ans_liquid=[l[x],l[y]]
    if total > 0:
        y-=1
    else:
        x+=1
print(*ans_liquid)

 

🧦 정렬 뒤, 두 용액의 합 total이 양수라면, 0에 더 가깝게 하기 위해 y를 왼쪽으로, 음수라면 0에 더 가깝게 하기 위해 x를 오른쪽으로 이동. 정렬되었으므로 전체 반복문을 돌 필요는 없다 (이미 더 크거나 작은 게 자명하므로)

---

★ 2467 용액 ★

 

import sys
input=sys.stdin.readline

N=int(input())
l=list(map(int,input().split()))
ans=2_000_000_001
x,y=0,(N-1)
ans_liquid=[]
while x<y:
    total=(l[x]+l[y])
    if abs(total) < ans:
        ans=abs(total) #ans update
        ans_liquid=[l[x],l[y]]
    if total > 0:
        y-=1
    else:
        x+=1
print(*ans_liquid)

 

🧦 위 2470 문제에서 정렬만 되어있으므로 정렬만 생략.

---

★ 2473 세 용액 ★

 

import sys
input=sys.stdin.readline

N=int(input())
arr=sorted(list(map(int,input().split())))
final_ans=100_000_000_000_000_000
for x in range(N):
    #find if y+z gets close to target
    ans=100_000_000_000_000_000
    target=(-arr[x])
    y,z=x+1,N-1
    while y<z:
        total=arr[y]+arr[z]
        if abs(total - target) < ans:
            ans = abs(total - target)
            if abs(arr[x]+total)< final_ans:
                final_ans=abs(arr[x]+total)
                ans_x_y_z=[arr[x],arr[y],arr[z]]
        if total > target:
            z-=1
        else:
            y+=1
print(*sorted(ans_x_y_z))

 

🧦 x고정하고 y와 z를 x+1, N-1로 설정해서 양쪽에서 중간으로 움직이면서 위 BOJ 2470 두 용액 문제의 투 포인터 알고리즘 그대로 사용. 이 때 두 용액의 합은 0이 아닌 -arr[x]와의 차이에 더 가까운지를 따져야 하고, 두 용액의 합이 -arr[x]보다 큰 지, 작은 지에 따라 두 포인터 이동 기준 정하면 된다.

---

★ 13144 List of Unique Numbers ★

 

import sys
input=sys.stdin.readline

N=int(input())
l=list(map(int,input().split()))
y=0
ans=0
kinds=set()
for x in range(N):
    ans+=(y-x)
    while y<N and l[y] not in kinds:
        kinds.add(l[y])
        ans+=1
        y+=1
    kinds.discard(l[x])
print(ans)

🧦 y가 1로 멈춘 상태에서 x가 2로 움직였을 때, 어차피 진행한 부분까지는 이미 모두 중복된 원소가 없음이 증명되었으므로(그러니까 y가 이동한 것이므로) x가 2일 때 2로 시작하는 부분연속수열(중복 없는 원소) [2], [2,3]은 개수 y-x로 굳이 y 다시 시작점 출발 필요 없이 ans에 자동으로 개수 더하면 된다.

---

★ 2230 수 고르기 ★

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
l=[int(input())for _ in range(N)]
l.sort()
ans=10_000_000_000
y=0
cumsum=0
for x in range(N):
    while y<N and cumsum<M:
        cumsum=(l[y]-l[x])
        y+=1
    if cumsum>=M:
        ans=min(ans,cumsum)
    if x<(N-1):
        cumsum-=(l[x+1]-l[x])
print(ans)

 

🧦 두 포인터를 왼쪽에서 시작해서 두 수의 차이가 M 이상이면서 제일 작은 차이를 구하는 문제. 

 

(1) 일단 오름차순 정렬

(2) x와 y 두 포인터 만들고, x는 0(index) 고정한 상태에서 y를 0(index)부터 오른쪽으로 차이가 M이상일 때까지 돌리기

(3) 그 다음 x 움직이면서 cumsum 빼고 현재 고정한 y에서 M이상일 때까지 또 돌리기

(4) 위 과정 반복하며 최종 ans update후 출력

+ 두 포인터 모두 각각 배열 전체를 한번씩만 돌리므로 시간 복잡도는 O(N+N+NlogN) (정렬 포함)

---

★ 1253 좋다 ★

import sys
input=sys.stdin.readline

N=int(input())
A=sorted(list(map(int,input().split())))
if N == 1 or N == 2: print(0); sys.exit()
ans=0
for i in range(N):
    res=False
    target=A[i]
    x,y=0,N-1
    if i == 0: x = 1
    elif i == N-1: y = N-2
    cursum=A[x]+A[y]
    while x<y:
        cursum=A[x]+A[y]
        if target==cursum:
            res=True
            break
        elif target<cursum:
            y-=1
            if y == i:
                y-=1
        else: #target>cursum
            x+=1
            if x == i:
                x+=1

    if res: ans += 1
print(ans)

 

🧦 N의 범위 2000이하이므로 O(N^2) 시간 복잡도 가능. 정렬한 뒤, 각 수를 target으로 잡고, target 이외의 배열 범위에서 투 포인터 진행. 이 때 정렬한 범위이므로, cursum이 target보다 크다면 y-=1 / 작다면 x+=1.

 

🧦 주의할 부분은, 나 자신 제외 다른 수들 중에서 합을 구하는 것이므로 y또는 x가 i일 때 추가로 y-=1 또는 x+=1 진행

 

🧦 시간복잡도 O(NlogN + N*(2*N))

---

★ 9024 두 수의 합 ★

def tp(l,i,j,K):
    ans=10**20
    ans_freq=0
    ans_updated=False
    while i<j:
        cur=l[i]+l[j]
        if cur==K:
            ans=0
            if not ans_updated:
                ans_updated = True
                ans_freq=1
            else:
                ans_freq+=1
            i+=1
        elif cur>K:
            if ans>abs(cur-K):
                ans=abs(cur-K)
                ans_freq=1
            elif ans==abs(cur-K):
                ans_freq+=1
            j-=1
        else: #cur<K
            if ans>abs(cur-K):
                ans=abs(cur-K)
                ans_freq=1
            elif ans==abs(cur-K):
                ans_freq+=1
            i+=1
    return ans_freq


import sys
input=sys.stdin.readline

t=int(input())
for _ in range(t):
    n,K=map(int,input().split())
    ns=sorted(list(map(int,input().split())))
    ans=tp(ns,0,n-1,K)
    print(ans)

 

🧦 두 수의 합이 K와 가장 가까운 두 수의 쌍의 개수를 구하는 문제

: 수를 모두 정렬한 뒤, nC2 brute-force O(n^2)으로 일일이 모든 쌍의 케이스를 고려할 필요 없이, 투 포인터 접근 방식 O(n)으로 만족하는 쌍의 개수를 구할 수 있다.

 

🧦 1 3 5 7 9가 있고 K를 10이라고 한다면, 투 포인터 i와 j를 양 옆 맨 끝에 놓는다.

(1) 포인터가 가리키는 두 수의 합이 K와 정확하다면 ans(K와의 차이 최솟값)을 바로 0으로 업데이트. flag 변수에 따라 ans_freq값을 +=1하거나 0으로 설정. 

(2) 포인터가 가리키는 두 수의 합이 K보다 작다면 ans를 업데이트할 지는 ans와 abs(K-두 수의 합)을 비교. ans보다 abs(K-두수의 합)이 작다면 업데이트 ans update하고 ans_freq=1, ans와 abs(K-두수의합)이 같다면 업데이트 필요 없이 기존 ans_freq+=1

(3) 포인터가 가리키는 두 수의 합이 K보다 크다면 위 (2)와 동일 메커니즘

 

※ 단, 투 포인터 접근 방식에 의해 (2)의 경우 오른쪽 포인터 j-=1 / (3)의 경우 왼쪽 포인터 i+=1 / (1)은 원하는대로 i+=1 또는 j-=1

 

🧦 투 포인터 접근이 가능한 이유: 1 3 5 7 9가 있고(list l, i는 0, j는 맨 끝) K를 9라고 한다면 l[i]+l[j]는 9보다 작다. 따라서 j를 아무리 왼쪽으로 옮겨도 9보다 더 작아기에 searching할 필요 x(우리는 최대한 K에 가까운 쌍의 개수만 원한다. 따라서 구한 쌍에서 쌍의 합이 더 작아지는 case는 searching할 필요 x - 투 포인터를 쓸 수 있는 이유). 따라서 j-=1하고 진행 / 반대로 K를 10이라고 한다면 l[i]+l[j]는 9보다 크다. 따라서 i를 아무리 오른쪽으로 옮겨도 9보다 더 커지기에 searching할 필요 x. 따라서 i+=1하고 계속 진행

---