백준 12891번 DNA 비밀번호
https://www.acmicpc.net/problem/12891

문제 접근

정해진 구간만큼을 움직이며 전체를 탐색하는 것
조건이 (1 ≤ |P| ≤ |S| ≤ 1,000,000) 이므로 시간 복잡도는 O(n)이어야 할 것. 최대 O(nlogn)가 되지 않을까. O(n^2)은 절대 안된다.

코드

from sys import stdin
input = stdin.readline

def is_good():
    for i in acgt:
        if now[i] < req[i]:
            return False
    return True

s, p = map(int, input().split())
dna = input().rstrip()
r = list(map(int, input().split()))
req = dict()
now = dict()
acgt = ["A", "C", "G", "T"]
for i in range(4):
    req[acgt[i]] = r[i]
    now[acgt[i]] = 0
ans = 0

for i in range(p):
    now[dna[i]] += 1
if is_good():
    ans += 1
for start in range(s - p):
    now[dna[start]] -= 1
    now[dna[start + p]] += 1
    if is_good():
        ans += 1


print(ans)

req : 구간이 만족해야 하는 조건을 저장한 dict
now : 현재 구간의 상태를 저장하는 dict
is_good() : 모든 A,C,G,T에 대해 now < req인지 검사하는 함수
조건보다 현재 상태가 작은 값을 가지는게 있다면 현재 구간은 조건을 만족하지 못한 것.
1. 첫 for문으로 0을 시작으로 하는 첫 구간을 검사한다.
2. 그 후 s - p만큼 반복하며 구간의 첫번째 값(가장 왼쪽)을 빼고 마지막 값의 그 다음 값(오른쪽)을 더하고 새로운 구간을 검사한다.

풀이

정해진 구간을 움직이면서 해당 구간을 탐색해야 한다고 생각했다. 시간복잡도가 O(n)이 되어야 한다고 생각하면서도 계속 O(n^2) 정도의 복잡도로 풀고 있었다. 예를 들어 내 나름대로 조금 시간 복잡도를 최적화 한다고 투포인터로 양끝에서 탐색하는 방식으로 접근도 해보았다.
하지만 내 생각의 근본적 문제점은 전체 s에서 p만큼의 구간을 이동하며 매번 해당 구간을 O(n)의 복잡도로 검사한 것이다...!

require = list(map(int, input().split()))
ans = 0
acgt = ["A", "C", "G", "T"]
for i in range(s - p + 1):
    s = i
    e = i + p - 1
    cnt = {"A": 0, "C": 0, "G": 0, "T": 0}
    is_ans = True
    while s < e:
        cnt[dna[s]] += 1
        cnt[dna[e]] += 1
        s += 1
        e -= 1
    if s == e:
        cnt[dna[s]] += 1
    for j in range(4):
        if cnt[acgt[j]] < require[j]:
            is_ans = False
    if is_ans:
        ans += 1

print(ans)

전혀 O(n) 알고리즘을 생각하지 못했다....
그래서 책을 살짝 보고 아이디어를 얻어 풀 수 있었다.
심지어 살짝 보고도 처음 생각한 건 현재 구간에서 나온 값들을 카운트하는게 아니라 조건의 숫자에서 빼는 방식으로 접근했다. 예를 들어 조건이 req = {"A":1, "C":0, "G":0, "T":1}일 때 구간에 A가 나오면 req["A"] -= 1을 했다. 이렇게 하니까 원래 조건이 0이었던게 나올 때 처리라던가 이미 0인 값을 어떻게 처리할 것인다 등 문제가 많았다. 그래서 결국 책의 풀이를 더 참고했다.

자잘하게 확인한 것
1. dict 초기화 방법
2. dict는 슬라이딩 안됨
3. collections의 Counter함수
4. dict 자체로 sum()은 안된다. .keys() 혹은 .values()
5. 반복 사용되는 A,C,G,T를 리스트에 넣어놓고 초기화하는데 쓰거나 하면 편한듯