백준 12891번 DNA 비밀번호 파이썬

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

12891번: DNA 비밀번호

 

내 답안

import sys
 
input = sys.stdin.readline
 
S, P = map(int, input().split())
DNA = input().rstrip()
DNA_dict = {'A': 0, 'C': 1, 'G': 2, 'T': 3}
ACGT = list(map(int, input().split()))
result = 0
 
start_index = 0
end_index = P - 1
 
check_list = [0, 0, 0, 0]
for i, j in enumerate('ACGT'): 
    check_list[i] = DNA[start_index: end_index + 1].count(j)
 
 
while S > end_index:
 
    start_index += 1
    end_index += 1
 
    if (ACGT[0] <= check_list[0] and ACGT[1] <= check_list[1] and ACGT[2] <= check_list[2] and ACGT[3] <= check_list[3]):
        result += 1
 
    check_list[DNA_dict[DNA[start_index - 1]]] -= 1
    try:
        check_list[DNA_dict[DNA[end_index]]] += 1
    except:
        continue
 
print(result)

---

Review

 

결론은 시간 복잡도 이슈로 인해 투포인터 방식으로 문제를 풀었다.

핵심은 check_list 를 만들어서 주어진 최소개수를 만족하는가에 초점을 두었다.

간단하게 나타낸다면 아래 사진 처럼 나타 낼 수 있다.

---

 

예제 입력으로 그림을 그려 설명을 하자면

# 예제 입력 2

4 2
GATA
1 0 0 1

코드 과정

 

 

* 코드에 예외 처리를 한 이유는 마지막 연산에서 Out-Of-Index 에러를 방지하기 위해서 예외를 하였다.

예외처리

---

 

처음에는 O(N^2) 으로 코드를 짰었다.

코드가 N^2 인것만 확인 하자!

# 시간초과 코드
 
import sys
 
input = sys.stdin.readline
 
S, P = map(int,input().split())
DNA = input().rstrip()
ACGT = list(map(int, input().split()))
result = 0
 
start_index = 0
end_index = P-1
 
while S-1 >= end_index:
    
    check_list = [0, 0, 0, 0]
    
    for i in range(start_index, end_index + 1):
        if DNA[i] == 'A':
            check_list[0] += 1
        elif DNA[i] == 'C':
            check_list[1] += 1
        elif DNA[i] == 'G':
            check_list[2] += 1
        elif DNA[i] == 'T':
            check_list[3] += 1
            
    if (ACGT[0] <= check_list[0] and ACGT[1] <= check_list[1] and ACGT[2] <= check_list[2] and ACGT[3] <= check_list[3]):
        result += 1
        
    start_index += 1
    end_index += 1
    
print(result)