백준 8933 : MCS (Python)

본문 링크

import sys
input=sys.stdin.readline
from collections import Counter

T=int(input())

for i in range(T):
    K,String=input().split()
    K=int(K)
    L="" ; dp=[0]*4 #A, G, T, C

    for i in range(K):
        L+=String[i]

        if String[i]=='A':
            dp[0]+=1
        elif String[i]=='G':
            dp[1]+=1
        elif String[i]=='T':
            dp[2]+=1
        elif String[i]=='C':
            dp[3]+=1
    start=0 ; end=K-1
    check=[]
    while end<len(String)-1:

        start+=1 ; end+=1
        L=L[1:] ; L+=String[end]
        check.append((dp[0], dp[1], dp[2], dp[3]))
        if String[start-1]=='A':
            dp[0]-=1
        elif String[start-1]=='G':
            dp[1]-=1
        elif String[start-1]=='T':
            dp[2]-=1
        elif String[start-1]=='C':
            dp[3]-=1

        if String[end]=='A':
            dp[0]+=1
        elif String[end]=='G':
            dp[1]+=1
        elif String[end]=='T':
            dp[2]+=1
        elif String[end]=='C':
            dp[3]+=1

    check.append((dp[0], dp[1], dp[2], dp[3]))
    counter = Counter(check)
    counter=counter.most_common(1)
    print(counter[0][1])

📌 어떻게 접근할 것인가?

전형적인 슬라이딩 윈도우 문제이다.
처음에 문제가 이해가 되지않았는데

예제 입력에서

• 3 GCAGGAGCGCCAGG

위와 같은경우 경우의 수는
["GCA" , "CAG" , "AGG" , "GGA" , "GAG" , "AGC" , "GCG" , "CGC" , "GCC" , "CCA" , "CAG" , "AGG"] 이다.

단 이때 모든 문자열을 비교할때는 정렬된 상태 에서 비교해야한다.
띠라서 GGA 와 GAG 는 서로 정렬했을때 AGG 이므로 두 문자열은 같다.

처음에는 슬라이딩 윈도우를 통해서 매번 똑같은 길이의 문자열을 구하고 그것을 정렬해서 딕셔너리에 저장까지했는데 , 시간초과가 발생했다.

문제에서는 문자의 종류가 딱 A, G, T, C 만 주기로 했으니
그 4개의 문자를 담을 $dp=[0]×4$ 을 만들어주고
check 라는 배열에다가 튜플형식으로 A , G , T , C 의 개수를 넣어준다.
이후 $Counter$ 라이브러리를 통해 중복되는 값의 개수를 구해준후
중복되는 값중의 최빈값을 구해줘수 출력해준다.