백준-12891(파이썬)

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

12891번: DNA 비밀번호

문제생각

 

입력받은 문자열을 슬라이싱하고 개수를 세고 조건을 확인하면 풀리는 간단한 문제라고 생각하고

바로 코드로 옮겼습니다.

 

역시 호락호락한 백준이 아닙니다.ㅎㅎ 바로 시간초과...

 

생각을 해보니 각 문자열은 한칸씩 다음 칸으로 옮겨지는 것이였습니다.

그럼 이전 부분문자열과 다음 부분문잘은 처음과 끝을 제외하고는 가운데 부분은 동일한 문자열인 것입니다.

그러면 굳이 또 문자열을 슬라이싱하고 반복문을 돌릴 필요없이 이전 부분문자열의 첫번째 문자를 빼고 다음 부분문자열의 마지막 문자를 더해주면 되는 것이였습니다.

문제코드

import sys
input=sys.stdin.readline

s, p=map(int, input().split()) #s:DNA문자열 길이, p:부분문자열의 길이
dnaStr=input()
check=list(map(int, input().split()))
ans=0
dic={'A':0, 'C':0, 'G':0, 'T':0}

def checkStr():
    global ans
    if dic['A']>=check[0] and dic['C']>=check[1] and dic['G']>=check[2] and dic['T']>=check[3]:
        ans+=1

temp=dnaStr[0:p] #첫번째 문자열 확인
for i in temp:
    dic[i]+=1
checkStr()

for i in range(1, s-p+1): #두번째부터 마지막까지 문자열 확인
    dic[dnaStr[i-1]]-=1 #이전 문자열의 첫번째 문자 하나 빼기
    dic[dnaStr[i+p-1]]+=1 #다음 문자열의 마지막 문자 하나 더하기
    checkStr() #문자열 확인

print(ans)

 

"아직 실력이 부족하여 문제 해결에 있어 코드가 매끄럽지 못한 점 양해부탁드립니다..ㅎ"