[python] 백준 12891 DNA 비밀번호

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

12891번: DNA 비밀번호

 

문제 해결

• 긴 문자열에서 정해진 문자열 개수 p로 자른 다음 개수를 확인하는 문제이다.
• 왼쪽부터 한 칸씩 문자열을 p개씩 슬라이싱 했을 때 주어진 조건을 만족시키면 가능한 경우의 수이므로 정답 +1씩 올린다.
• 문자열은 한칸씩 이동하므로 한번 0~p-1까지 문자를 확인한다음 가장 왼쪽 인덱스의 문자를 제외시키고 오른쪽에 한칸 씩 문자를 추가시킴으로써 계산을 최소화 시킬 수 있다.
• 인덱스는 'A'와 같은 문자보다 0, 1, 2 를 쓰는 것이 편할 경우가 많지만 문자를 0, 1, 2 와 같은 인덱스로 변환시켜야 할 때가 있으므로 translate리스트를 통해서 'A' <->0, 'C'<->1, 'G' <->2, 'T' <->3 을 편하게 변환시킬 수 있도록 한다.

 

CODE

 

import sys

input = sys.stdin.readline
ans = 0
s, p = map(int, input().split())
string = str(input().rstrip())
need = list(map(int, input().split())) # 'A', 'C', 'G', 'T' 필요개수
now = {0:0, 1:0, 2:0, 3:0} # 현재 개수
translate = ['A', 'C', 'G', 'T'] # 인덱스 변환 도구로 활용
for i in range(p):
    now[translate.index(string[i])] += 1
for i in range(4):
    if now[i] < need[i]:
        break
else:
    ans += 1
for i in range(s-p):
    now[translate.index(string[i])] -= 1
    now[translate.index(string[i+p])] += 1
    for j in range(4):
        if now[j] < need[j]: break
    else:
        ans += 1
print(ans)