[Problem Solving] BOJ 12891 : DNA 비밀번호

문제 링크 : https://www.acmicpc.net/problem/12891

 

A, C, G, T로만 이루어진 문자열에서 각 문자의 최소 개수를 만족하는 부분 문자열의 개수를 구하는 문제이다. 단순한 패턴매칭으로 풀면 N은 최대 100만, M도 최대 100만이기 때문에 O(NM) 만큼이 걸려 시간초과가 발생한다. 

슬라이딩 윈도우 방법을 사용하면 선형 시간 안에 해결이 가능하다.

윈도우를 이동시키면서 윈도우에 포함된 A, C, G, T의 개수를 조정한다. 조정 후에 최소 개수를 만족한다면 answer를 1 증가시킨다.

윈도우 이동이 끝나면 answer를 출력한다.

 

import sys

read = sys.stdin.readline

S, P = map(int, read().split(" "))
DNAString = read().rstrip()
A, C, G, T = map(int, read().split(" "))

cntA = 0
cntC = 0
cntG = 0
cntT = 0
answer = 0

for i in range(P):
    if DNAString[i] == 'A':
        cntA += 1
    elif DNAString[i] == 'C':
        cntC += 1
    elif DNAString[i] == 'G':
        cntG += 1
    elif DNAString[i] == 'T':
        cntT += 1

if cntA >= A and cntC >= C and cntG >= G and cntT >= T:
    answer += 1

for i in range(P, S):
    if DNAString[i] == 'A':
        cntA += 1
    elif DNAString[i] == 'C':
        cntC += 1
    elif DNAString[i] == 'G':
        cntG += 1
    elif DNAString[i] == 'T':
        cntT += 1

    if DNAString[i - P] == 'A':
        cntA -= 1
    elif DNAString[i - P] == 'C':
        cntC -= 1
    elif DNAString[i - P] == 'G':
        cntG -= 1
    elif DNAString[i - P] == 'T':
        cntT -= 1

    if cntA >= A and cntC >= C and cntG >= G and cntT >= T:
        answer += 1
    

print(answer)