728x90
반응형
문자열, 슬라이딩 윈도우 문제이다.
슬라이딩 윈도우는 고정된 범위를 가지고 어떤 리스트나 문자열 등을 한칸씩 옆으로 옮겨가며 조건을 검사하는 알고리즘을 뜻한다.
# 문자열, 슬라이딩 윈도우
from collections import deque
import sys
input = sys.stdin.readline
S, P = map(int, input().split()) # DNA 길이, 비번 길이
DNA = input().strip()
ACGT = list(map(int, input().split()))
def slidingWindow():
# 결과 담을 변수
result = 0
# 큐에 초기값 집어넣기
queue = deque()
for i in range(P):
queue.append(DNA[i])
# ACGT 개수 미리 세놓기
A = queue.count('A')
C = queue.count('C')
G = queue.count('G')
T = queue.count('T')
idx = P # 다음 문자 가져올 인덱스
# 빠져나가는 것과 들어오는 알파벳의 개수만 변화시킨다
while queue:
if A >= ACGT[0] and C >= ACGT[1] and G >= ACGT[2] and T >= ACGT[3]:
result += 1
# 앞 문자열을 뺀다
string = queue.popleft()
if string == 'A': A -= 1
elif string == 'C': C -= 1
elif string == 'G': G -= 1
elif string == 'T': T -= 1
# 뒤에 문자열을 더한다
if idx >= len(DNA): # 남은 DNA문자가 없으면 break
break
string2 = DNA[idx]
queue.append(string2)
if string2 == 'A': A += 1
elif string2 == 'C': C += 1
elif string2 == 'G': G += 1
elif string2 == 'T': T += 1
idx += 1 # 다음 문자열을 가리키도록 인덱스 증가
return result
print(slidingWindow())
큐를 사용했고, 부분 문자열을 미리 큐에 담아놓는다. 큐에 담겨진 문자의 개수가 만족된다면 result에 1을 더해준다.
이때 각 ACGT 각 문자의 개수는 처음에 딱 한번 미리 count 함수로 구해 놓는다.
이후 조건을 검사한 후 맨 앞 문자를 빼고 다음 문자를 뒤에 추가한다. 이 때 부분 문자열에서 단 2개의 문자만이 바뀌는 것이므로, 이 2개 문자만 검사하고 어떤 문자냐에 따라서 ACGT의 개수를 변경만 해주면 된다. 즉 항상 count함수로 모든 문자를 검사할 것 없이 바뀌는 앞,뒤 문자 2개만 검사하면 되는 것이다.
만약 매번 count로 검사한다면 최악 복잡도는 O(N^2)이 되어 문제를 해결할 수 없다.
슬라이딩 윈도우 기법으로 앞,뒤 문자만을 검사할 경우 문자열을 딱 한번 순회하며 O(N)으로 끝낼 수 있다.
참고로 DNA 문자열 입력 받을 때, strip()이나 rstrip()을 붙여줘야 한다. 붙이지 않으면 \n 개행문자가 추가되고 오답 처리를 받는다.
728x90
반응형