https://www.acmicpc.net/problem/12891
12891번: DNA 비밀번호
평소에 문자열을 가지고 노는 것을 좋아하는 민호는 DNA 문자열을 알게 되었다. DNA 문자열은 모든 문자열에 등장하는 문자가 {‘A’, ‘C’, ‘G’, ‘T’} 인 문자열을 말한다. 예를 들어 “ACKA”
www.acmicpc.net
시간초과 때문에 고생을 많이 한 문제인데 푼 방법을 보면 너무 일차원적이라서 허무했다.
하지만 다시한번 생각해보면 일차원적인 방법이 더 빠르다는것을 한번에 알 수 있다.(처음 방법은 쓸데없는 과정이 있음)
슬라이딩 윈도우를 이용한 풀이법으로 슬라이딩 윈도우는 일정 간격을 일정하게 움직여가며 탐색하는 방법이다.
아래 그림과 같이 3칸의 범위를 일정하게 움직이는 방법이다.
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
처음에는 움직일 범위의 리스트를 슬라이싱하여 비밀번호에 적합한지 검사하는 방법을 생각했지만 시간초과가 났고 생각해보니 할때마다 범위를 슬라이싱할 필요 없이 맨 왼쪽끝 인덱스는 삭제하고 맨 오른쪽 끝 인덱스를 추가하면 훨씬 간편하게 비밀번호를 검사할 수 있다.
코드는 다음과 같다.
import sys
input = sys.stdin.readline
s, p = map(int, input().split()) ## 임의, 비번
DNA_string = list(input().rstrip())
DNA = [0, 0, 0, 0]
min_num = list(map(int, input().split())) ## A, C, G ,T
start = 0
end = p
count = 0
def DNA_count(start, end):
global count
global DNA
for i in range(start, end):
if DNA_string[i] == 'A':
DNA[0] += 1
elif DNA_string[i] == 'C':
DNA[1] += 1
elif DNA_string[i] == 'G':
DNA[2] += 1
else:
DNA[3] += 1
if (DNA[0] >= min_num[0]) and (DNA[1] >= min_num[1]) and (DNA[2] >= min_num[2]) and (DNA[3] >= min_num[3]):
count += 1
DNA_count(start, end)
for i in range(end, s):
if DNA_string[i] == 'A':
DNA[0] += 1
elif DNA_string[i] == 'C':
DNA[1] += 1
elif DNA_string[i] == 'G':
DNA[2] += 1
elif DNA_string[i] == 'T':
DNA[3] += 1
if DNA_string[i-p] == 'A':
DNA[0] -= 1
elif DNA_string[i-p] == 'C':
DNA[1] -= 1
elif DNA_string[i-p] == 'G':
DNA[2] -= 1
elif DNA_string[i-p] == 'T':
DNA[3] -= 1
if (DNA[0] >= min_num[0]) and (DNA[1] >= min_num[1]) and (DNA[2] >= min_num[2]) and (DNA[3] >= min_num[3]):
count += 1
print(count)
if문이 너무 많아서 일차원적이지만 이것저것 리스트를 자르고 하는것이 아니라 인덱스로 접근하여 바로 따질수 있기때문에 빠르다.
'algorithm > baekjoon' 카테고리의 다른 글
[백준 17298번] 오큰수 (Python/파이썬) (0) | 2023.01.20 |
---|---|
[백준 11003번] 최솟값 찾기 (Python/파이썬) (0) | 2023.01.17 |
[백준 1253번] 좋다 (Python/파이썬) (0) | 2023.01.09 |
[백준 1940번] 주몽 (Python / 파이썬) (0) | 2023.01.07 |
[백준 2018번] 수들의 합 5 (파이썬/Python) (0) | 2023.01.07 |