[백준] 12891번 - DNA 비밀번호

---

문제 분석

P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다. 이때 부분 문자열의 길이가 P이므로 슬라이딩 윈도우의 개념을 이용하여 문제를 쉽게 해결할 수 있다.

---

소스 코드

# DNA 비밀번호

import sys
input = sys.stdin.readline

checkList = [0]*4
myList = [0]*4
checkSecret = 0

# 함수정의


def myadd(c):  # 새로 들어온 문자를 처리하는 함수
    global checkList, myList, checkSecret
    if c == 'A':
        myList[0] += 1
        if myList[0] == checkList[0]:
            checkSecret += 1
    elif c == 'C':
        myList[1] += 1
        if myList[1] == checkList[1]:
            checkSecret += 1
    elif c == 'G':
        myList[2] += 1
        if myList[2] == checkList[2]:
            checkSecret += 1
    elif c == 'T':
        myList[3] += 1
        if myList[3] == checkList[3]:
            checkSecret += 1


def myremove(c):  # 제거되는 문자를 처리하는 함수
    global checkList, myList, checkSecret
    if c == 'A':
        if myList[0] == checkList[0]:
            checkSecret -= 1
        myList[0] -= 1
    elif c == 'C':
        if myList[1] == checkList[1]:
            checkSecret -= 1
        myList[1] -= 1
    elif c == 'G':
        if myList[2] == checkList[2]:
            checkSecret -= 1
        myList[2] -= 1
    elif c == 'T':
        if myList[3] == checkList[3]:
            checkSecret -= 1
        myList[3] -= 1


S, P = map(int, input().split())
Result = 0
A = list(input())
checkList = list(map(int, input().split()))

for i in range(4):
    if checkList[i] == 0:
        checkSecret += 1

for i in range(P):  # 초기 P 부분 문자열 처리 부분
    myadd(A[i])
if checkSecret == 4:
    Result += 1

for i in range(P, S):
    j = i-P
    myadd(A[i])
    myremove(A[j])
    if checkSecret == 4:
        Result += 1

print(Result)

---

이 문제를 풀면서 고려해준 사항은 다음과 같다.

먼저 처음의 부분 문자열이 주어진 DNA 문자열의 조합에 해당하는 지를 검사한다. (이때 A,C,G,T 테이블을 만든다)

이후 부분 문자열의 크기는 동일하게 유지하며 한칸씩 우측으로 밀어주는 과정을 진행하며, 이때 추가되는 문자, 삭제되는 문자에 따라 포함되는 A,C,G,T 테이블의 값들을 수정하는 과정을 거친다.

즉, 추가되고 삭제되는 문자들에 대해서 어떠한 과정을 통해 테이블을 수정할지에 대한 고민이 필요하다.