12891번: DNA 비밀번호

문제링크: https://www.acmicpc.net/problem/12891

투포인터의 응용버전 슬라이딩 윈도우 입니다. 투포인터가 특정 조건에서만 한 포인터를 옮겨주었다면, 슬라이딩 윈도우는 매번 두 포인터가 같이 움직이면서 포인터간의 간격을 일정하게 유지합니다.

Problem

처음엔 염기서열의 길이와 Key의 길이가 주어지고, 그다음 염기서열과 Key에 필요한 필수원소가 ACGT순으로 주어집니다. 염기서열 안 어떤 substring에 필수원소 갯수가 충족되면, 그것은 valid한 Key가 됩니다. 이러한 Key들의 갯수를 찾으면 되겠습니다.

Approach & Solution

보자마자 슬라이딩 윈도우 문제라는것을 직감했습니다. Key의 길이가 고정이기 때문이죠. 그래서 가벼운 마음으로 풀었는데 시간초과가 나버렸습니다.

from collections import Counter
import sys
input = sys.stdin.readline
dna = {
  'A':0,
  'C':0,
  'G':0,
  'T':0
}
result = 0
n,end = map(int,input().split())
start = 0
chromo = input()
temp = list(map(int,input().split()))
j = 0
for i in dna.keys():
  dna[i] += temp[j]
  j +=1

while end <= len(chromo):
  target = Counter(chromo[start:end])
  if target['A'] >= dna['A'] and target['C'] >= dna['C'] and target['G'] >= dna['G'] and target['T'] >= dna['T']:
    result += 1

  start += 1
  end += 1

print(result)

슬라이딩 윈도우의 시간 복잡도는 문자열을 처음부터 끝까지 한번만 거쳐가므로 O(n)입니다. 하지만 여기서 제가 Counter를 이용해서 Key값과 비교를 하려했기 때문에 추가로 O(n)이 붙게됩니다. 따라서 총 시간복잡도는 O(n^2)이 되면서 시간초과가 나게 됩니다. 이러면 슬라이딩 윈도우를 쓰는 이유가 없는거겠죠..ㅎㅎ 그래서 Counter를 사용하지 않고 구현해 보았습니다.

dna = {
  'A':0,
  'C':0,
  'G':0,
  'T':0
}
result = 0
n,end = map(int,input().split())
end -= 1
start = 0
chromo = input()
a,c,g,t = list(map(int,input().split()))
target = chromo[start:end]

for i in target:
  dna[i] += 1

while end < len(chromo):

  dna[chromo[end]] += 1
  
  if dna['A'] >= a and dna['C'] >= c and dna['G'] >= g and dna['T'] >= t:
    result += 1

  dna[chromo[start]] -=1
  
  start += 1
  end += 1

print(result)

대략적으로 설명하자면, dna 안에 substring의 염기 갯수를 담아줍니다. 그 dictionary를 필요원소 갯수와 비교해서, 충족하면 result += 1을 해주면서 카운트해줍니다. 카운트가 끝났다면, 왼쪽 염기서열을 빼주고 오른쪽 염기서열 하나를 붙히면서 반복문을 돌게 됩니다.

Conclusion

이 문제에 슬라이딩 윈도우는 어렵지않게 들어있는것 같습니다. 다만, 문제 자체를 구현하는데 조금은 서툴고, Counter를 자주 사용했는데, 시간 복잡도가 초기화하는데 O(n)이 들기때문에 조금은 조심해서 쓰는게 좋겠습니다!