IOIOI[71]

IOIOI

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

문제

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이 몇 군데 포함되어 있는지 출력한다.

풀이

• 문자열을 돌아가면서 IOI패턴을 찾고 그 패턴이 이어지는 count를 센다.
• 패턴의 count가 N보다 크면 count
• 총 count를 세면 S에 몇개의 PN이 숨어있는지 확인할수 있다.
• 시간복잡도 O(M)

N = int(input())
M = int(input())
S = input()
patternCount = 0
count = 0
index= 1
while index < M-1:
    #1~m-2까지
    if S[index-1] == 'I' and S[index] == 'O' and S[index+1] == 'I':
        patternCount +=1
        if patternCount >=N:
            count+=1
        index+=1
    else :
        patternCount = 0
    index+=1
print(count)