[5525] IOIOI

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

 

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

 

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

 

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

서브태스크

 

예제 입력 1

1
13
OOIOIOIOIIOII

 

예제 출력 1

4

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

 

예제 입력 2

2
13
OOIOIOIOIIOII

 

예제 출력 2

2

• OOIOIOIOIIOII
• OOIOIOIOIIOII

 

풀이

서브태스크를 모두 충족하려면 시간 복잡도를 낮춰야 했는데, 여러번 시도해도 못풀어서 다른 분의 코드를 보고 겨우 이해했다..

연속되는 'IOI' 개수를 체크하는 것인데, 만약 'IOI'이면 연속되는 'IOI'의 수인 P를 증가시키고 인덱스를 2개 넘긴다

그후, 원하는 N의 값인지 체크한 후 맞다면  num을 증가시키고 P를 감소시켜서 구했다 이렇게 해야 시간복잡도를 낮추고 서브태스크 2까지 충족시킬 수 있다

 

N = int(input())
M = int(input())
S = input()
num = 0
P = 0
i = 0

while i < (M - 1):
    if S[i:i+3] == 'IOI':
        i += 2
        P += 1
        if P == N:
            num += 1
            P -= 1
    else:
        i += 1
        P = 0
        
print(num)