★Two-Pointers Advanced I - 7 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에 자동으로 개수 더하면 된다.

---