[백준/Python] 5525. IOIOI

※ 문제

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

※ 문제 유형

문자열 (SILVER_1)

※ 나의 풀이

• 시간 복잡도를 고려하지 않고, index slicing을 통해 문제 해결 하였을 시, 50점

import sys

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

find_s = 'IOI' + 'OI' * (N-1)

ans = 0
idx = 0
while idx < len(S) - len(find_s):
    if S[idx : idx + len(find_s)] == find_s:
        ans += 1
        idx += 1
    idx += 1
print(ans)

• 시간 복잡도를 고려하여, 인덱스 슬라이싱을 진행할 때, 중복된 IOI를 체크해야 하는 과정을 줄이기 위하여 다른 방안 채택
• 투 포인터 알고리즘 고려

import sys

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

find_s = 'IOI' + 'OI' * (N-1)

ans = 0
idx = 0
cnt = 0
while idx + 3 <= M:
    if S[idx : idx + 3] == 'IOI': # IOI 패턴 찾기
        idx += 2
        cnt += 1
        # IOI + 뒤에 IOI 가 나오는 횟수를 cnt
        # cnt 가 N이라면, 우리가 찾는 IOI + OI * (N-1)
        if cnt == N:
            ans += 1
            cnt -= 1 # 누적된 IOI 개수를 -1
    
    else:
        idx += 1
        cnt = 0
print(ans)