[백준] 12891번 DNA 비밀번호 파이썬 코드

코드

# 특정 배열에서 크기가 고정인 부분 배열을 빠르게 처리해야한다 -> 슬라이딩 윈도우

from collections import deque

n,m = map(int, input().split())
dnastring = input()
cntlst = [*map(int, input().split())]
cnt = 0
nstr = deque(dnastring[:m])

numdict = {"A":0, "C":0, "G":0, "T":0}
for i in nstr:
  if i == "A":
    numdict[i] +=1
  elif i == "C":
    numdict[i] +=1
  elif i == "G":
    numdict[i] +=1
  elif i == "T":
    numdict[i] +=1

if numdict["A"] >= cntlst[0] and numdict["C"] >= cntlst[1] and numdict["G"] >= cntlst[2] and numdict["T"] >= cntlst[3]: cnt = 1

for i in range(1, n-m+1):
  numdict[nstr.popleft()] -= 1
  nstr.append(dnastring[m+i-1])
  numdict[nstr[-1]] += 1
  if numdict["A"] >= cntlst[0] and numdict["C"] >= cntlst[1] and numdict["G"] >= cntlst[2] and numdict["T"] >= cntlst[3]: cnt += 1
print(cnt)

count 함수를 사용하면 시간 복잡도O(N^2)이기 때문에 미리 값을 구해두고 처음 값을 빼고 마지막 들어오는 값을 더해주는 방식을 선택해야한다. 문자열 슬라이싱하는 것이 머리 아파서 덱을 이용해 해결했다. 인덱스 구하는 게 왜이렇게 헷갈리는지...