[백준 5525] 파이썬 - ioioi

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

5525번: IOIOI

 

1. 코드설명

# 50점

n = int(input())

m = int(input())

s = input()

i = 0

count = 0

pn = 'IO'*n + 'I'

while i < m - len(pn) :

    if s[i:i+2*n+1] == pn :

        i += 2

        count += 1

    else:

        i += 1

print(count)

 

# 100점

n = int(input())

m = int(input())

s = input()

answer = 0

i = 0

count = 0

while i <= m:

    if s[i:i+3] == 'IOI':

        i += 2

        count += 1

        if count == n: # ioi 반복이 pn에 도달했을 경우

            answer += 1 

            count -= 1 

    else:

        i += 1

        count = 0

print(answer)

 

 

2. 주의사항

 

pn의 문자열을 직접 생성하고 s 문자열의 인덱스마다 비교하는 1번 방법은 n이 커지면 시간초과가 발생한다

 

따라서 pn은 ioi 의 조합임을 활용하여 시간복잡도 문제를 해결한다.