12891 DNA 비밀번호 (슬라이딩 윈도우)

계속 시간 초과가 났던 문제이다. 아마도 비교하는 DICTIONARY를 계속해서 초기화 했기 때문이다. 슬라이딩 윈도우 문제인데 데이터 통신 강의때도 접했던 적이 있다. 범위를 조정해가면서 일정 부분만큼 앞에서 뺀 뒤, 뒤로 붙이는 작업이다.

1st에서의 값이 2st에서 존재하지만, 맨 앞의 c 값은 제거되며 index를 하나 옮긴 G값은 생성된다.
즉, 코드의 else문에서 앞의 값을 딕셔너리에서 제거해야한다는 것이다.

s, p = map(int, input().split(" "))
st = input()
A, C, G, T = map(int, input().split(" "))
lis = [A,C,G,T]
dic = {"A":lis[0], "C":lis[1], "G":lis[2], "T":lis[3]} ##{'A': 1, 'C': 0, 'G': 0, 'T': 1}
cnt = 0
res = {"A": 0, "C": 0, "G": 0, "T": 0}

for i in range(len(st) - p + 1):
    flag = True

    if i == 0:
        for j in range(p):
            res[st[j]] += 1
    else:
        res[st[i+p-1]] += 1
        res[st[i-1]] -= 1

    for j in ('A','C','G','T'):
        if dic[j] > res[j]:
            flag = False
            break
    if flag:
        cnt += 1

print(cnt)