[Python][백준/BOJ] 12891번 : DNA 비밀번호

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

12891번: DNA 비밀번호

 

내 코드

시간 초과된 코드

import sys
input = sys.stdin.readline

s, p = map(int, input().split())
dna =list(input().strip('\n'))
a,c,g,t = map(int, input().split())

window = dna[:p]
cnt =0
for i in range(p, len(dna)):
    window.append(dna[i]) #p번쨰
    window[i-p] ='0'
    if window.count('A') >= a and window.count('C') >= c and window.count('G') >= g and window.count('T') >= t:
        cnt +=1
print(cnt)

 

통과된 코드

import sys
input = sys.stdin.readline

s, p = map(int, input().split())
dna = str(input().rstrip())
word2 = list(map(int, input().split()))
comp = {'A':0, 'C':0, 'G':0, 'T':0}
tmp = dna[:p]
cnt= 0
for i in tmp:
    comp[i] +=1
if comp['A'] >= word2[0] and comp['C'] >= word2[1] and comp['G'] >= word2[2] and comp['T'] >= word2[3]:
    cnt+=1

for i in range(s-p):
    comp[dna[i]] -=1
    comp[dna[i+p]] +=1
    if comp['A'] >= word2[0] and comp['C'] >= word2[1] and comp['G'] >= word2[2] and comp['T'] >= word2[3]:
        cnt+=1
print(cnt)

 

코드 리뷰

이 문제를 푸는데 꼬박 1일이나 걸렸다.. 슬라이딩 윈도우를 쉽게 보고 바로 풀기 시작했지만, 문자열 슬라이딩 윈도우는 숫자와 조금 다른 부분이 있었다. 이제 문자를 만나도 두렵지 않다..!

막상 풀어보니 쉽다...사람들이 열심히 풀어놓았던데, 구글링을 해도 온전히 내 것이 잘 안 돼서 끙끙대다가 다른 사람들보다 비교적 더 쉽게 푼 것 같다.

슬라이딩 윈도우

이 문제는 구간이 정해져 있기 때문에 투포인트보다 슬라이딩 윈도우 알고리즘으로 푸는 것이 더 효율적이다. 하지만 숫자일 때와 조금 다르게 풀어야 한다.

문자가 들어간다는 점에서 부분 합을 요구하지 않고, sum을 사용하지 않는다.

comp = {'A':0, 'C':0, 'G':0, 'T':0}

처음에 이 dictionary를 생각해내지 못해서 시행착오가 많았던 것 같다.

시간 초과가 났을 때부터 list로 해결하는 것은 잘못되었다고 생각하고, dict로 바꾸기 시작했다.

이 dictionary는 (앞으로 움직일) 구간 안에 해당 문자가 몇 개 있는지 저장하려고 만들었다.

그리고 tmp라는 배열을 만들어서 구간이 정해진 문자형 윈도우를 만들어주었다.

for i in tmp:
    comp[i] +=1
if comp['A'] >= word2[0] and comp['C'] >= word2[1] and comp['G'] >= word2[2] and comp['T'] >= word2[3]:
    cnt+=1

처음 등장하는 이 for문은 0~m까지의 첫 구간때문에 만들었다.  

첫 구간을 한 번 쭉 돌리면서, 해당 문자가 몇 개 있는지 검사하고, 검사가 끝나면 각 문자가 모두 최소 개수를 넘는지 확인한다. 넘으면 비밀번호를 만들 수 있으므로 cnt+1 을 해준다.

for i in range(s-p):
    comp[dna[i]] -=1
    comp[dna[i+p]] +=1
    if comp['A'] >= word2[0] and comp['C'] >= word2[1] and comp['G'] >= word2[2] and comp['T'] >= word2[3]:
        cnt+=1

이건 s-p에서 조금 막혔던 것 같다. 길이가 총 s이고, 이 안에서 p개를 빼서 윈도우를 만들거라면 윈도우의 개수는 총 s-p개가 나올 수 있다. 한마디로 윈도우 개수만큼 돌려주는 것이다.

그리고 문자열이기 때문에 dict를 이용해서 + - 연산을 해준다.

i는 0부터 시작하니까 dna[0]은 윈도우를 한 칸 옆으로 옮길 때 더 이상 필요없는 문자다. 그러니까 dict에서도 이를 생각해서 해당 문자를 카운팅해주었던 값에서 1을 빼준다. 

그리고 마찬가지로 한 칸 옆으로 옮기니까 새로 등장하는 문자(dna[i+p])에 해당하는 문자를 comp에서 찾아서 +1 해준다.

윈도우가 움직일 때마다 이렇게 딱 두 개만 검사해서 체크해주면 된다. 그러므로 for문 이런거 필요 없이 바로 if문 써서 비밀번호 만들 수 있는지 체크해주고 가능하다면 cnt +1 한다.

하루나 걸렸는데 풀어보니 너무 쉽다. 다음부터는 더 빨리 풀 수 있을 것 같다.

 

슬라이딩 윈도우 알고리즘 (Sliding Window)

슬라이딩 윈도우에 대한 설명은 여기서 확인할 수 있다.