알고리즘 자료구조 - 백준 12891번- DNA 비밀번호, 투 포인터

백준의 12891번은 투포인터 알고리즘입니다.

우선 투포인터를 사용하지 않은 코드를 보여드리겠습니다.

import sys 
input = sys.stdin.readline
info = list(map(int,input().split()))
m,n = info[0],info[1]

li = input()
info2 = list(map(int,input().split()))
a,c,g,t = info2[0], info2[1], info2[2], info2[3]
s = 0; e = n; count = 0
while True:
    re1 = li[s:e].count('A')
    re2 = li[s:e].count('C')
    re3 = li[s:e].count('G')
    re4 = li[s:e].count('T')
    if (re1>=int(a))&(re2>=int(c))&(re3>=int(g))&(re4>=int(t)):
        count += 1
    if e == m :
        print(count)
        break
    s += 1; e += 1

이렇게하면 이해하기는 쉽지만 매번 원하는 모든 자리수의 값을 세어 계산하기 때문에 문제가 원하는 2초에 맞출 수 없습니다.

이때 사용할 수 있는 투포인터에 대해 설명하겠습니다. 이 알고리즘은 배열의 같은 위치에서 시작하여 서로 다른 방향으로 진행하는 투 포인터를 사용합니다.

1. 배열의 양 끝에서 같은 위치에서 시작합니다. 따라서 두 포인터의 초기 위치는 0이나 배열의 길이에 위치하게 됩니다.
2. 두 포인터는 서로 다른 방향으로 진행하며 배열을 탐색합니다.
3. 특정 조건을 만족할 때까지 포인터들을 이동시킵니다.
4. 조건을 만족하는 부분을 찾으면 해당 부분을 처리하거나 결과를 반환합니다.
5. 필요에 따라 포인터를 다음 위치로 이동하여 계속 탐색합니다.

예를 들어, 배열에서 합이 특정 값과 일치하는 두 원소를 찾거나 특정 패턴을 탐색할 때 이 알고리즘을 사용할 수 있습니다. 이때, 포인터들은 배열을 순차적으로 탐색하면서 조건을 만족하는 부분을 찾습니다.

이 문제에서 첫번째 포인터를 인덱스 0번, 두번째 포인터를 인덱스 p에 놓고 문자열을 오른쪽으로 한칸씩 이동해가며 제일 왼쪽에 있는 글자를 빼고 추가된 데이터를 더하는 식의 투포인터 계산을 해야 원하는 시간에 맞출 수 있습니다.

아래는 투포인터를 사용한 코드입니다.

#import sys 
#input = sys.stdin.readline
info = list(map(int,input().split()))
m,n = info[0],info[1]

li = input()
info2 = list(map(int,input().split()))
a,c,g,t = info2[0], info2[1], info2[2], info2[3]
s = 0; e = n; count = 0
re1 = li[s:e].count('A')
re2 = li[s:e].count('C')
re3 = li[s:e].count('G')
re4 = li[s:e].count('T')
if (re1>=int(a))&(re2>=int(c))&(re3>=int(g))&(re4>=int(t)):
    count += 1

    
for i in range(0,m-e):
    if li[s+i] == 'A' :
        re1 -= 1
    elif li[s+i] =='C':
        re2 -= 1
    elif li[s+i] =='G':
        re3 -= 1
    elif li[s+i] =='T':
        re4 -= 1
    else :
        pass
    
    if li[e+i] == 'A' :
        re1 += 1
    elif li[e+i] =='C':
        re2 += 1
    elif li[e+i] =='G':
        re3 += 1
    elif li[e+i] =='T':
        re4 += 1
    else:
        pass
    
    
    print(i)
    print(s,e)
    if (re1>=int(a))&(re2>=int(c))&(re3>=int(g))&(re4>=int(t)):
        count += 1
print(count)