[백준 파이썬 12891번]좋다★DNA 비밀번호★WINDOWS SLIDING★VER2.0★시간초과 고려

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

12891번: DNA 비밀번호

DNA

VERSION 2.0

 

import sys
from collections import Counter

S, P = map(int , sys.stdin.readline().split(' '))
DNA = list(map(str, sys.stdin.readline().rstrip()))
find = dict(zip(['A' , 'C' ,'G' , 'T'] ,list(map(int, sys.stdin.readline().split(' ')))))
res = 0
start_idx , end_idx = 0 ,0
base = {'A' : 0 , 'C' : 0 , 'G' : 0 , 'T' : 0}
for start_idx in range(S-P+1): #3번 , 9 8 이라면 , 9-8+1 = 2번 ,

    flag = True


    if start_idx == 0:
        for idx in range(P):
            base[DNA[idx]]+=1 #start_idx가 0 , 시작 지점일때 , 잘리는 곳 까지 +1 시킨다.
    else:
        base[DNA[start_idx + P - 1]] +=1 #start_idx가 1~ 일경우 DNA 리스트의 있는 맨끝자리만 +=1 시켜줘야한다.
        base[DNA[start_idx-1]] -=1 #start_idx 의 0부분 과 같이 이전 부분은 자른다.

    for t in list(find.keys()):
        if base[t] < find[t]:
            flag = False

            break
    if flag:
        res+=1
print(res)
#%%

==> WINDOWS SLIDING의 경우 고정된 리스트에서 맨 앞꺼 하나씩 자르고, 뒤에꺼 추가하는 방식이다!!!

 

 

시간초과

 

VERSION 1.0

 

import sys
from collections import Counter

S, P = map(int , sys.stdin.readline().split(' '))
DNA = list(map(str, sys.stdin.readline().rstrip()))
find = dict(zip(['A' , 'C' ,'G' , 'T'] ,list(map(int, sys.stdin.readline().split(' ')))))
res = 0
i = 0
while True:
    j = P+i
    if j <= S :
        DNA_cut = DNA[i:j]
        d = dict(Counter(DNA_cut))
        res+=1
        i+=1
        for k,v in d.items():
            # print(d[k])
            if d[k] < find[k]:
                res-=1
                break
    else:
        break
print(res)

#%%

==> dict(zip(리스트1 , 입력받는 리스트) )

 

==> 리스트 split ==> [시작 인덱스 : 끝 인덱스+ 1]