자료구조-슬라이딩 윈도우

이론

📖 슬라이딩 윈도우?
2개의 포인터로 범위를 지정한 다음, 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘

문제풀이

📖 백준 12891 (🔗백준 12891 문제)

✏ O(n) 시간복잡도알고리즘 사용.

✏ 윈도우를 한 칸씩 이동하면서 현재 상태리스트를 업데이트.
이때 삽입되는 문자열과 삭제되는 문자열만 보고 업데이트한다.
그 후, 비밀번호가 유효한 지 확인.

#슬라이딩 윈도우
#상태리스트업데이트(한칸씩이동)를 하고 유효 비밀번호 검사할 때, 새로 들어온 문자열과 제거되는 문자열만 확인할 것

import sys
input=sys.stdin.readline

s,p=map(int,input().split())
dna=list(input())
check_pw=list(map(int,input().split()))
pw=[0]*4
count_check=0
result=0

def add(i):
	global pw,check_pw,count_check
	if(i=='A'):
		pw[0]+=1
		if(pw[0]==check_pw[0]):
			count_check+=1
	elif(i=='C'):
		pw[1]+=1
		if(pw[1]==check_pw[1]):
			count_check+=1
	elif(i=='G'):
		pw[2]+=1
		if(pw[2]==check_pw[2]):
			count_check+=1
	elif(i=='T'):
		pw[3]+=1
		if(pw[3]==check_pw[3]):
			count_check+=1

def remove(i):
	global pw,check_pw,count_check
	if(i=='A'):
		if(pw[0]==check_pw[0]):
			count_check-=1
		pw[0]-=1
	elif(i=='C'):
		if(pw[1]==check_pw[1]):
			count_check-=1
		pw[1]-=1
	elif(i=='G'):
		if(pw[2]==check_pw[2]):
			count_check-=1
		pw[2]-=1
	elif(i=='T'):
		if(pw[3]==check_pw[3]):
			count_check-=1
		pw[3]-=1

for i in range(p):
	add(dna[i])

for i in range(4):
	if(check_pw[i]==0):
		count_check+=1

if (count_check==4):
	result+=1

for i in range(p,s):
	add(dna[i])
	remove(dna[i-p])
	if (count_check==4):
		result+=1

print(result)

📖 백준 11003 (🔗백준 11003 문제)

✏ 정렬 사용x
정렬은 시간복잡도가 O(nlogn)이므로, N 과 L의 최대 범위가 5,000,000인 조건에서는 정렬을 사용하면 안된다.

✏ 덱(DEQUE) 사용.
정렬을 사용할 수 없으므로, 덱을 이용해 사용한다.

• 덱의 마지막위치에서부터 현재테스트값보다 큰값은 제거하고 마지막 위치에 현재테스트값 삽입.
• 덱의 1번째부터 L의 범위를 벗어난 경우 덱에서 제거.
• 덱의 1번째 데이터값 출력.

#슬라이딩윈도우, 정렬
#정렬은 O(nlogn)의 시간복잡도를 가지므로, 정렬을 사용할 수 없다.
#덱(deque)사용하기

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

n,l=map(int,input().split())
test=list(map(int,input().split()))
result=deque()

for i in range(n):
	while result and result[-1][0]>test[i]:
		result.pop()
	result.append((test[i],i))
	
	if(result[0][1]<=i-l):
		result.popleft()
	print(result[0][0],end=" ")
    

❗ DEQUE(덱)

DEQUE(덱)? 양 끝에서 데이터를 삽입하거나 삭제할 수 있는 자료구조.
왼쪽에서는 appendleft() : 삽입, popleft() : 삭제.
오른쪽에서는 append() : 삽입, pop() : 삭제.

덱에서는 (인덱스,숫자) 형태의 노드를 사용한다.

◼ 참고사항

• Do it! 알고리즘 코딩테스트
• 백준