[백준] 5525번 IOIOI

💡문제접근

• 인덱스로의 접근을 시도했으나 문자열 S의 길이가 최대 1,000,000까지이고 결국 시간초과(TLE)가 발생하게 된다.
• 문자열 탐색 알고리즘으로 KMP 알고리즘이 있다고 해서 추가로 공부했다. 구글링을 통해서 시간초과를 해결할 수 있는 방법을 찾아서 풀고 이해했던 문제였다.

💡코드(메모리 : 33212KB, 시간 : 268ms)

import sys
input = sys.stdin.readline

N = int(input().strip())
M = int(input().strip())
S = input().strip()

t = 0
cnt = 0
res = 0
while t < M-1:
    if S[t:t+3] == "IOI":
        cnt += 1
        t += 2
        if cnt == N:
            res += 1
            cnt -= 1
    else:
        t += 1
        cnt = 0
print(res)

💡소요시간 : 47m