IOIOI

5525번: IOIOI

 

나의 풀이

import sys
input = sys.stdin.readline

n = int(input())
str_len = int(input())
rt_str = input().rstrip()

patten_ct = 0
result = 0
idx = 0

while idx <= (str_len-1):
    if rt_str[idx:idx+3] == 'IOI':
        patten_ct += 1
        idx += 2
        if patten_ct == n:
            result += 1
            patten_ct -= 1
    else:
        patten_ct = 0
        idx += 1
print(result)

 

시간 복잡도

while idx <= (str_len-1) : 단어를 순회하며 패턴을 찾으므로 ( 선형시간 복잡도 )
해당 알고리즘 시간 복잡도는 : 선형시간 복잡도 ( O(n) )