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

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

12891번: DNA 비밀번호

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

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

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

 

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