[백준] 12891 DNA 비밀번호 - Python

문제

이 문제는 주어진 문자열의 길이가 100만 까지 제한이 있으므로 O(n)의 시간 복잡도 알고리즘으로 해결해주어야 합니다.

따라서, 모든 경우의 수를 따질 수 없게 되고, 이는 슬라이딩 윈도우를 활용하여 해결할 수 있습니다.

슬라이딩 윈도우는 2개의 포인터로 범위를 지정한 다음, 이 범위를 유지한채로 문제에서 주어지는 특정 조건을 만족하도록 구현하는 것 입니다. 코드를 통해 알아보도록 하겠습니다.

Python

#비밀번호
def is_valid_password(check, a, c, g, t):
    if check['A']>=a and check['C']>=c and check['G']>=g and check['T']>=t:
        return True
        
s,p=map(int,input().split())

dna_str=input()

a,c,g,t=map(int,input().split())

cur_checklist={
    'A': 0,
    'C': 0,
    'G': 0,
    'T': 0
}
tmp=dna_str[:p]

for i in tmp:
    if i in cur_checklist.keys():
        cur_checklist[i]=cur_checklist.get(i,0)+1

cnt=0
if is_valid_password(cur_checklist, a, c, g, t):
    cnt+=1

s_idx=0
e_idx=s_idx+p

#크기를 유지하며 이동한다.
for i in range(s-p):
	#새로 들어온 값과 제거된 값을 업데이트 해준다.
    cur_checklist[dna_str[s_idx+i]]-=1 #제거되는 문자열
    cur_checklist[dna_str[e_idx+i]]+=1 #새로 들어온 문자열
    if is_valid_password(cur_checklist, a, c, g, t):
        cnt+=1
print(cnt)

1. 문제에서 주어지는 문자열의 길이와, 부분 문자열의 길이를 입력받습니다.

2. 문제에서 주어지는 문자열을 입력받습니다.

3. A,C,G,T의 최소 개수를 입력 받습니다.

4. 부분 문자열의 길이 만큼 문자열을 순회하기 위해 문자열 슬라이싱을 활용해줍니다.

5. 부분 문자열을 순회하며, A,C,G,T의 개수를 구해줍니다. 이 때, 각 문자에 맞는 개수를 저장하기 위해 딕셔너리를 활용해 줍니다.

6. 문제에서 주어진 조건(A,C,G,T의 최소 개수 이상을 가지는지)을 만족하는지 확인하기 위해 is_valid_password() 함수를 호출하여 검증해줍니다. 검증 결과가 참이게 되면, 경우의 수를 하나 증가해줍니다.

7. 문제의 핵심 부분 입니다. 슬라이딩 윈도우는 크기를 유지하며 이동하게 되고, 이동한 뒤에는 제거된 문자열과 새로 들어온 문자열의 값을 업데이트 해주어야 합니다.

8. 이동한 뒤에는 is_valid_password 함수를 다시 호출하여 A,C,G,T가 특정 개수 이상인지 검증해줍니다. 결과값이 참이면, 경우의 수를 하나 증가해 줍니다.