[백준] 12891번 DNA 비밀번호(python)

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

12891번: DNA 비밀번호

 

1. 난이도 실버2 (🥈) 

 

2. 문제 해결 방법

부분문자열의 크기가 1,000,000으로 크기 때문에 시간복잡도 O(n) 으로 해결해야한다.

 

따라서 슬라이딩 윈도우 + 딕셔너리를 이용해서 문제를 해결했다.

 

(다른 푼들이 푸는 코드를 보니 단순하게 if elif를 사용하는게 더 이득이었던 거 같음,,)

 

1. DNA라는 딕셔너리를 선언해주고, 첫 start 부터 end까지의 염기 개수를 카운팅해준다.

 

2. 현재 범위의 ACGT의 개수가 최솟값보다 작을 경우 check를 count해준다.

 

3. check가 0인 경우는 ACGT모두 조건에 만족한다는 의미기 때문에 answer+=1 해주고, end와 start를 이동해준다.

 

4. start 자리에 있던 염기 값 -1, end자리에 새로 올 염기값 +1 을 해준다. (이걸 end가 끝으로 갈 때까지 반복)

 

 

3. 내가 작성한 코드

s,p = map(int, input().split()) #s=전체문자열 p=부분문자열
answer = 0

dna = {"A" : 0,
       "C" : 0,
       "G" : 0,
       "T" : 0}

entity = list(input())

for i in entity[:p]: #처음 염기서열 개수를 딕셔너리에 저장
  if i == "A":
    dna["A"] += 1
  elif i == "C":
    dna["C"] += 1
  elif i == "G":
    dna["G"] += 1
  else:
    dna["T"] +=1

minimum = list(map(int, input().split())) #만족해야 하는 값

start = 0
end = p-1

while True:
  check = 0
  
  for i in range(4): #ACGT의 개수를 비교하며 조건을 만족하지 못하면 check 
    alpha = ["A","C","G","T"]
    if dna[alpha[i]] < minimum[i]:     
      check+=1

  if check == 0: #모든 염기서열이 조건을 만족한 경우 count
    answer+=1

  if end == s-1: #끝에 도달했을 경우 break
    break

  dna[entity[start]] -= 1
  start+=1
  end+=1
  dna[entity[end]] += 1
  
print(answer)