[백준] 12891번 : DNA 비밀번호 - 파이썬(Python) - 우당탕탕 개발자 되기 프로젝트

 

12891번: DNA 비밀번호

 

1. 문제 설명

2. 풀이과정

P와 S의 길이가 1,000,000으로 매우 크기 때문에 O(n)의 시간 복잡도 알고리즘으로 문제를 해결해야 한다.

부분 문자열의 길이가 P이므로 슬라이딩 원도우의 개념을 이용해 문제를 쉽게 해결할 수 있다.

슬라이딩 윈도우 알고리즘은 2개의 포인터로 범위를 지정한 다음 범위를 유지한 채로 이동하며 문제를 해결하는 알고리즘이다.

먼저 문자열의 시작 위치에 포인터를 하나 두고, 부분 문자열의 길이만큼 뒤에 포인터를 하나 두어 범위를 지정한다.

이후 앞쪽 포인터와 뒤쪽 포인터를 같이 뒤로 옮기면서 범위는 유지한 채로 새로운 부분 문자열을 만든다.

새로운 부분 문자열에서 포함되어야 할 문자의 개수를 변경하며 최소 개수 이상으로 있는지 확인한다.

이때 매번 새 부분 문자열의 각 문자를 세지 말고, 처음 부분 문자열에서만 개수를 세어 저장한 다음 그 뒤로는 양끝 문자를 제외, 포함하면서 문자 1개에 대한 개수만 변경한다.

 

슈도코드

1. S(문자열 크기), P(부분 문자열의 크기) 입력받기
2. st(문자열 데이터) 입력받기
3. min_count(비밀번호의 각 문자 최소 개수 조건) 입력받기
4. answer(비밀번호 종류의 개수) 초기화
5. s(부분 문자열의 시작 포인터) = 0
6. e(부분 문자열의 끝 포인터) = P
7. check(부분 문자열에 들어있는 각 문자의 개수 리스트)
8. 각 문자의 개수를 부분 문자열에서 세어 저장 (초기 1회만 수행)
9. while (True)
10. 비밀번호 종류 1 증가
11. for i 각 문자별 반복
12. if (최소 개수가 부분 문자열에 들어 있는 개수보다 많으면) : 비밀번호 아니므로 종류 1 감소, 비밀번호 판별 종료
13. if (부분 문자열의 끝 포인터가 문자열의 끝을 넘어가면) : 비밀번호 찾기 종료
14. 부분 문자열의 시작 포인터가 가리키는 문자를 부분 문자열에 들어 있는 문자의 개수에서 감소시킴 (시작 문자 제외)
15. 부분 문자열의 시작 포인터 뒤로 이동 s += 1
16. 부분 문자열의 끝 포인터가 가리키는 문자를 부분 문자열에 들어 있는 문자의 개수에서 증가시킴 (끝 문자 새로 포함)
17. 부분 문자열의 끝 포인터 뒤로 이동 e += 1
18. 최종 비밀번호 종류 출력

반응형

3. 소스코드

import sys

S, P = map(int, sys.stdin.readline().split())
st = sys.stdin.readline().rstrip()
min_count = list(map(int, sys.stdin.readline().split()))

answer = 0

s = 0
e = P

check = [0] * 4
check[0] = st[s : e].count('A')
check[1] = st[s : e].count('C')
check[2] = st[s : e].count('G')
check[3] = st[s : e].count('T')

while (True):
    answer += 1
    for i in range(4):
        if (min_count[i] > check[i]):
            answer -= 1
            break

    if (e >= S):
        break

    if (st[s] == 'A'):
        check[0] -= 1
    elif (st[s] == 'C'):
        check[1] -= 1
    elif (st[s] == 'G'):
        check[2] -= 1
    elif (st[s] == 'T'):
        check[3] -= 1
    s += 1
    
    if (st[e] == 'A'):
        check[0] += 1
    elif (st[e] == 'C'):
        check[1] += 1
    elif (st[e] == 'G'):
        check[2] += 1
    elif (st[e] == 'T'):
        check[3] += 1
    e += 1

print(answer)