[Do-it! 코딩 테스트-기초편] 009. DNA 비밀번호

문제

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

12891번: DNA 비밀번호

---

접근

 

---

코드

import sys

S, P = map(int, sys.stdin.readline().split(' '))
DNA = input()
DNA_list = list(map(int, sys.stdin.readline().split(' ')))
# 1
DNAdict = {"A": 0, "C": 0, "G": 0, "T": 0}
start = 0
end = P-1
cnt = 0
# 2
for i in DNA[start:end + 1]:
    DNAdict[i] += 1
# 3
if DNAdict["A"] >= DNA_list[0] and \
        DNAdict["C"] >= DNA_list[1] and \
        DNAdict["G"] >= DNA_list[2] and \
        DNAdict["T"] >= DNA_list[3]:
    cnt += 1
# 4
while end != S - 1:
    DNAdict[DNA[start]] -= 1
    DNAdict[DNA[end + 1]] += 1
    if DNAdict["A"] >= DNA_list[0] and \
            DNAdict["C"] >= DNA_list[1] and \
            DNAdict["G"] >= DNA_list[2] and \
            DNAdict["T"] >= DNA_list[3]:
        cnt += 1
    start += 1
    end += 1

print(cnt)

---

설명

DNA_list => ACGT 최소 개수 입력

 

# 1

구간별로 ACGT 개수를 세기 위해 딕셔너리 선언, 구간(윈도우)을 나타내는 포인터 선언

조건을 만족하는 개수를 세는 cnt 선언

 

# 2

맨 처음 구간은 반복문을 따로 돌려서 ACGT 개수를 셈.

구간을 도는 i가 딕셔너리 key(A, C, G, T)와 같을 때 그 value를 하나 증가시킨다.

 

# 3

구한 ACGT 개수 딕셔너리와 입력한 DNA_list를 비교하여 모든 원소가 최소 개수 이상이면

cnt += 1

 

# 4

윈도우 시작 포인터와 끝 포인터를 증가시켜서 윈도우를 이동하며 각 부분이 조건에 맞는지 확인하는 과정이다.

윈도우를 왼쪽으로 한 칸 이동하면 맨 왼쪽 값이 빠지고 오른쪽에 새로운 값이 생긴다.

두 값의 변화를 DNAdict에 최신화 해주는 과정을 추가한다.

DNAdict[DNA[start]] -= 1

DNAdict[DNA[end + 1]] += 1

바뀐 딕셔너리와 DNA_list를 비교하여 새로운 윈도우에서 조건이 맞는지 확인한 후 cnt값을 조작한다.

---

알고리즘

투 포인터