5525번 IOIOI

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

---

아이디어

n = int(input())
m = int(input())
s = input().rstrip()

# Pn이 뭔지 구하기
temp = 'I'
temp += 'OI' * n
cnt = 0
for i in range(0, m+1):
    if temp == s[i:i+2*n+1]:
        cnt += 1
print(cnt)

처음에 이렇게 풀었다가 50점 맞았다.

arr [a:b]의 시간 복잡도 : O(b - a)

O(m*n)이라서 시간초과가 난 것 같다.

그래서 다른 방법을 생각했다.(정답 코드)
current는 현재 보고 있는 인덱스이고 IOI의 개수를 센다.
왜냐하면 Pi는 IOI의 개수가 i개이다.
이때 현재 IOI의 개수를 세는 게 cnt이고 만약 IOI를 찾았다면 현재 보고 있는 인덱스 + 2해서 또 훑는다.
만약 cnt가 n이라면 answer + 1한다.

이때 시간복잡도는 O(m)

---

코드

n = int(input())
m = int(input())
s = input().rstrip()

current, answer, cnt = 0, 0, 0

while current <= m-3:
    if s[current:current+3] == 'IOI':
        cnt += 1
        current += 2
        if cnt == n:
            answer += 1
            cnt -= 1 # 연속일수도 있음
    else:
        current += 1
        cnt = 0
print(answer)