백준 / IOIOI / 5525

Question

문제링크
Silver 2

Logic

기본 구조 : o(n)
1. 첫 풀이는 투 포인터를 이용해 P(N)과의 1대1 비교를 이용했었다.

from sys import stdin

N = int(stdin.readline().strip())
M = int(stdin.readline().strip())
S = stdin.readline().strip()

target = 'I'+'OI'*N
i,j = 0,2*N+1
res = 0
while j <= M+1 :
    if target == S[i:j] : res +=1
    i,j = i+1, j+1

print(res)

하지만 이는 시간복잡도를 해결하지 못했다.
2. 따라서 직접 연산이 필요했다. 'IOI'라는 패턴이 몇 번 반복하는지 세고, 동시에 패턴의 갯수가 N과 같다면 P(N)이 한 개 존재한다. 이는 탐색과 동시에 이뤄져야 하므로, 이 경우 패턴 -1 하고 정답 갯수 +1 해야 한다.

Code

from sys import stdin

N = int(stdin.readline().strip())
M = int(stdin.readline().strip())
S = stdin.readline().strip()

cnt,ans,i = 0,0,0
while i < M-2 :
    if S[i]=='I' and S[i+1]=='O' and S[i+2]=='I' :
        cnt+=1
        if cnt==N:
            cnt-=1
            ans+=1
        i += 2
    else : 
        cnt=0
        i += 1

print(ans)