👩‍💻🔠 [baekjoon] 12891번: DNA 비밀번호

🖍️ solution

import sys
from collections import Counter, deque

"""
[시간]
1) 21:30 ~ 22:00

[요약]
1) DNA 문자열: A, C, G, T로만 구성된 문자열
    => DNA 문자열의 일부를 뽑아 비밀번호로 사용
    => 추출 기준은 서로 다른 문자의 개수가 특정 개수 이상 등장해야 함
    => 만들 수 있는 비밀번호 종류, 추출된 위치가 다르면 문자열이 같아도 다른 비밀번호로 취급
[전략]
1) collections.Counter 사용
    - 처음 슬라이딩 부분까지만 계산
"""
S, P = map(int, sys.stdin.readline().split())
dna = sys.stdin.readline().rstrip()
chars = ['A', 'C', 'G', 'T']
result, minimal = 0, {k: v for k, v in zip(chars, list(map(int, sys.stdin.readline().split())))}

counter = Counter(dna[:P])
for i in range(P-1, S):
    if i != P-1:
        counter[dna[i-P]] -= 1
        counter[dna[i]] += 1
    checker = True
    for char in chars:
        if counter[char] < minimal[char]:
            checker = False
            break
    if checker:
        result += 1
print(result)

💡 idea

• 1) Sliding Window 사용
  • 개별 윈도우에 포함된 철자의 개수를 세어 기준치를 넘기는지 대조
    • Time Complexity 고려해, collections.Counter는 처음 윈도우에 한 번 사용
      • Input이 백만까지라서 모든 윈도우에 Counter 적용하면 O(n^2)으로 시간 초과 발생할 가능성 있음
    • 이후 윈도우를 옮기면서 변화되는 철자의 개수만 수정
      • 맨 앞의 철자에 대한 개수를 한 개 빼주고, 앞으로 추가될 철자의 개수를 하나 늘려준다

비밀번호라고 판정하는 기준이 특정 철자의 개수라는 점에 유의해, 슬라이딩 윈도우를 변형하면 시간 초과되지 않고 문제를 해결할 수 있다.