[백준] 12891번 DNA 비밀번호(python)

1. 문제

https://www.acmicpc.net/problem/12891

2. 풀이

슬라이딩 윈도우를 사용하여 문제를 풀면 된다.
https://ji-musclecode.tistory.com/37 블로그를 참고하였다.

초기에 문자열 자체를 길이만큼 순회하면서 count를 사용해 갯수 조건이 맞으면 cnt 값을 증가시키는 방식으로 진행했고 시간초과가 났다.

A, C, G, T 가 담긴 딕셔너리를 통해 초기 부분 문자열의 갯수를 확인한 후
조건(갯수 비교) 이 만족하는 지 확인한다
이후 슬라이딩 윈도우를 통해 하나씩 이동하므로 빠져나가는 앞자리에 대한 건 빼고 새로 들어오는 뒷자리는 더한다 이후 그에 해당하는 조건을 검사하는 것을 반복하며 조건에 맞는다면 cnt를 증가시킨다.

3. 코드

import sys

s, p = map(int, sys.stdin.readline().strip().split())
dna = sys.stdin.readline().strip()
a,c,g,t = map(int, sys.stdin.readline().strip().split())

cnt = 0
current = {'A':0, 'C':0, 'G':0, 'T':0}

for i in range(p):
    current[dna[i]] += 1

def check():
    return current['A'] >= a and current['C'] >= c and current['G'] >= g and current['T'] >= t

# 초기값 확인
if check():
    cnt += 1

# 슬라이딩 윈도우 도입
for i in range(p, s):
    current[dna[i - p]] -= 1
    current[dna[i]] += 1

    # 윈도우 검사
    if check():
        cnt += 1

print(cnt)

초기 시간 초과 코드

import sys

s, p = map(int, sys.stdin.readline().strip().split())
dna = sys.stdin.readline().strip()
a,c,g,t = map(int, sys.stdin.readline().strip().split())

cnt = 0
for i in range(0, s - p + 1):
    # print(dna[i:i + p])
    partstr = dna[i:i + p]
    acnt = partstr.count('A')
    ccnt = partstr.count('C')
    gcnt = partstr.count('G')
    tcnt = partstr.count('T')

    if acnt >= a and ccnt >= c and gcnt >= g and tcnt >= t:
        cnt += 1
print(cnt)