소스 코드

import sys
input = sys.stdin.readline

N = int(input().rstrip())
M = int(input().rstrip())
S = input().rstrip()

idx = 0
acc_IOI = 0
result = 0

# 선형적으로 순회하면서, IOI 를 찾는다.
# IOI를 발견하면 그 오른쪽으로 idx를 옮기는게 아닌,
# IOI 에서 세 번째 위치에 있는 I 위치로 idx를 옮겨서,
# 다시 IOI를 검사하도록 한다.
# 이런 식으로 탐색했을 때, 연속으로 IOI를 체크한 횟수로
# P인지 여부를 판정한다.
# 시간복잡도는 O(N^3)

while idx < M:
    if S[idx:idx + 3] == "IOI":
        acc_IOI += 1
        idx += 2

        if acc_IOI == N:
            result += 1
            acc_IOI -= 1

    else:
        acc_IOI = 0
        idx += 1

print(result)

풀이

1. 주어진 S를 왼쪽부터 선형적으로 순회하며 다음울 수행한다.

   1) idx로부터 3개만큼의 문자열이 IOI인지 검사한다. 만약 맞다면 연속된 IOI의 개수를 기록하는 변수에 1을 더하고, idx를 2 증가시킨다. (idx를 2 증가시키는 것이 핵심이다. 예를 들어 IOIOI에서 왼쪽의 IOI 부분을 판정했을 때, idx는 중간의 I 위치로 가게 되고, 그 때 다시 한번 오른쪽 부분의 IOI를 판정하게 되어, acc_IOI는 2가 될 것이다.)

   2) IOI가 아니라면, idx를 1 증가시키고, 연속 개수를 0으로 초기화시킨다.

   3) 만약 연속 IOI 개수가 N과 같다면, 이는 P 이므로 적절히 카운팅해준다. 이 때, 다음 단계로 넘어가며 idx를 증가시키면서 제일 좌측의 IOI가 빠지므로, 연속 카운팅에서 1을 빼준다.

어려웠던 점, 배운 점

1. 단순 순회 풀이를 생각했을 때, TLE가 난다고 생각해서 다른 풀이를 생각했었는데, 알고보니 저런 아이디어가 있었다.. 핵심을 생각해내지 못해서 못 푼 문제였다.

2. 이 풀이를 생각해내지 못하고 다른 풀이를 생각했는데, 그 풀이는 S에서 "IO" 부분을 모두 "T"로 치환하고, 그 이후에 위 풀이와 유사한 느낌으로 푸는 방식으로 제출했었다. 테케는 모두 통과하고, 시간복잡도도 O(N)인 풀이라고 생각하는데, 왜 통과가 안되는지 그 이유는 잘 모르겠다...