백준 12891 DNA 비밀번호 파이썬

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

12891번: DNA 비밀번호

처음에는 문제를 주어진 문자열 속에서 P개의 문자를 뽑아 비밀번호를 만든다로 해석을 잘 못해 조합을써서 풀었더니 시간초과를 맛봤다.

그래서 왜 시간초과가 나는지 이해 못 했고 다른 사람들 풀이를 보니 문제가 부분 문자열 즉 이어진 문자만 가능하다는 것이였다.. 이 사실을 알고 문제 분류에 맞게 슬라이딩 윈도우 방법으로 풀어봤다.

 

코드 설명을 간단하게 하자면 우선 꼭 들어가야하는 문자의 개수가 입력으로 주어지고 부분 문자열 중에서 그 문자가 주어진 숫자보다 많으면 된다는 것을 알았다.

그래서 [A,C,G,T]순서대로 입력 받았으니 A가 나오면 A자리에 -1 A가 지워지면 +1 해주는 형식으로 가능한 모든 경우를 탐색해봤다. 탐색하는 도중에 가능한 비밀번호의 개수를 체크해야하니 리스트 안에 0보다 큰 수가 있으면 조건에 안 맞는 비밀번호이기 때문에  리스트 안에 0보다 큰 수가 있으면 0을 리턴해주고 없으면 1을 리턴해주는 함수를 만들어 더해줬다.

 

def de(s,p): #빼주고 더해주는 함수
    if p ==1:#문자 넣기
        if s=='A':
            ct[0]-=1
        elif s=='C':
            ct[1]-=1
        elif s=='G':
            ct[2]-=1
        elif s=='T':
            ct[3]-=1
    else:#문자 빼기
        if s=='A':
            ct[0]+=1
        elif s=='C':
            ct[1]+=1
        elif s=='G':
            ct[2]+=1
        elif s=='T':
            ct[3]+=1

def ch(s): #조건에 맞는 비밀번호인지 확인해주는 함수
    for i in s:
        if i>0:
            return 0
    return 1

a,b = map(int,input().split())
s = input()
ct =list(map(int,input().split()))#조건
re = 0
for i in range(b):#초기 문자열
    de(s[i],1)
re += ch(ct)
for i in range(b,a):
    de(s[i-b],0)#빼기 +1
    de(s[i],1)#넣기 -1
    re+=ch(ct)#확인
print(re)