[백준 12891번] DNA 비밀번호 (Python/파이썬)

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

12891번: DNA 비밀번호

시간초과 때문에 고생을 많이 한 문제인데 푼 방법을 보면 너무 일차원적이라서 허무했다.

하지만 다시한번 생각해보면 일차원적인 방법이 더 빠르다는것을 한번에 알 수 있다.(처음 방법은 쓸데없는 과정이 있음)

슬라이딩 윈도우를 이용한 풀이법으로 슬라이딩 윈도우는 일정 간격을  일정하게 움직여가며 탐색하는 방법이다.

 

예시로 아래 그림과 같이 3칸의 범위를 일정하게 움직인다

처음에는 움직일 범위의 리스트를 슬라이싱하여 비밀번호에 적합한지 검사하는 방법을 생각했지만 시간초과가 났고 생각해보니 할때마다 범위를 슬라이싱할 필요 없이 맨 왼쪽끝 인덱스는 삭제하고 맨 오른쪽 끝 인덱스를 추가하면 훨씬 간편하게 비밀번호를 검사할 수 있다.

코드는 다음과 같다.

 

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문이 너무 많아서 일차원적이지만 이것저것 리스트를 자르고 하는것이 아니라 인덱스로 접근하여 바로 따질수 있기때문에 빠르다.