📌 Problem.

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

$P_N$ = IOIOI...OI (O가 N개)인 수열 $P_N$이 있다.
I와 O로 구성된 문자열 S에 들어 있는 $P_N$의 개수를 출력한다.

📌 Solution.

1 ≤ N ≤ 1000000, 2N+1 ≤ M ≤ 1000000를 만족하면 100점,
N ≤ 100, M ≤ 10000만을 만족하면 50점인 문제이다.

1. (50점)

import sys

input = sys.stdin.readline
N = int(input())
M = int(input())
S = input().rstrip()
p = 'I' + 'OI' * N

count = 0
for start in [i for i in range(M - len(p) + 1) if S[i] == 'I']:
    end = start + len(p)
    if S[start:end] == p:
        count += 1
print(count)

1번 코드는 O(N^2)이 소요되므로 50점짜리 코드이다.
매번 문자열을 2N + 1 길이만큼 슬라이싱하기 때문이다.

2. (100점)

import sys

input = sys.stdin.readline
N = int(input())
M = int(input())
S = input().rstrip()
left, right = 0, 0
answer = 0

while right < M:
    if S[right:right + 3] == 'IOI':
        right += 2
        if right - left == 2 * N:
            answer += 1
            left += 2
    else:
        left = right = right + 1

print(answer)

2번 코드는 1번 코드에 반해, 투 포인터로 중복되는 슬라이싱 연산들을 줄여 O(N)이 소요된다.

가령, N = 2이고 S = 'IOIOIOI'라고 하자.
1번 코드는 IO(IOI)OI의 가운데 괄호 친 부분을 중복해서 슬라이싱한다.
반면, 2번 코드는 S를 3개씩만 쭉 슬라이싱하므로 중복이 매우 적다.

3개씩 슬라이싱하면서 주어진 조건을 잘 검사하는 것이 핵심이다.