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

슬라이딩 윈도우 알고리즘은 2개의 포인터를 사용한다는 점에서 투 포인터와 유사하지만, 2개의 포인터 사이의 간격이 일정하게 유지된다는 점에서 차이가 있습니다. 포인터가 이동하는 모습이 마치 창문을 이동시키는 모양새와 같다고 해서 슬라이딩 윈도우라는 이름으로 불리게 되었습니다.

슬라이딩 윈도우 방식으로 문제를 풀 때 가장 중요한 점은, 새롭게 추가되는 원소와 제거되는 원소만으로 결과를 얻어야 한다는 것입니다. 이러한 이유에서 Deque 자료구조가 슬라이딩 윈도우에서 유용할 수 있습니다.

1. DNA 비밀번호

>> 백준 12891번 / 실버 5

1) Problem

2) Test Case

3) Solution

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

S, P = map(int, input().split()) # DNA 문자열의 길이, 부분 문자열의 길이
lst = list(input().strip()) # DNA 문자열

A, C, G, T = map(int, input().split()) # A, C, G, T의 최소 개수
result = {'A':0, 'C':0, 'G':0, 'T': 0}

deq = deque(lst[:P]) # 윈도우를 deque로 변환
cnt = 0

for i in deq: # Deque는 인덱스 연산이 비효율적이므로, for i in range(len(deq))를 쓰지 않도록 함.
    result[i] += 1

if result['A'] >= A and result['C'] >= C and result['G'] >= G and result['T'] >= T:
        cnt += 1 # 조건을 만족할 경우 cnt 증가

for i in range(P, S):
    # 윈도우 슬라이딩
    result[deq.popleft()] -= 1
    deq.append(lst[i])
    result[lst[i]] += 1

    if result['A'] >= A and result['C'] >= C and result['G'] >= G and result['T'] >= T:
        cnt += 1

print(cnt)

① dic = {'A': 0, 'C': 0, 'G': 0, 'T': 0}

• A, C, G, T 각각의 개수를 저장하기 위한 딕셔너리를 초기화한다.
• 초기에는 모든 값이 0으로 설정되어 있다.

② dq = deque(dna_str[left:right])

• 파이썬에서 슬라이싱의 범위는, 왼쪽 경계는 포함하고 오른쪽 경계는 포함하지 않는다는 것에 주의한다.

2. 최소값 찾기

>> 백준 10003번 / 플래티넘

1) Problem

2) Test Case

3) Solution

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

count, window_size = map(int, input().split()) # 숫자의 개수, 윈도우의 크기
dq = deque() # deque의 원소는 [index][숫자]의 구조체 형식으로 저장할 예정임
num_list = list(map(int, (input().split()))) # 숫자 리스트

for i in range(count):
  # 인덱스가 윈도우를 벗어나면(i-window_size보다 dq의 첫번째 원소의 인덱스가 작으면) 해당 원소를 삭제
  if dq and dq[0][0] <= i-window_size:
    dq.popleft()

  # 들어올 원소가 dq의 가장 오른쪽 원소(-1번 인덱스)의 값보다 작으면 기존 원소 삭제
  while len(dq) >= 1 and num_list[i] < dq[-1][1]:
    dq.pop()

  # dq에 원소를 넣음
  dq.append((i, num_list[i]))
  
  print(dq[0][1], end = " ") # 줄 바꿈없이 공백 추가