[python3] 백준 5525번 - IOIOI

문제

일단 가장 먼저 떠오르는 방법은 문자열 슬라이싱을 통해 비교하는 방법이다.

n,m = [int(input()) for _ in range(2)]
s = input()
cnt = 0
pn = 'I'
for _ in range(n):
    pn += 'OI'

for i in range(m):
    if s[i]=='I':
        if s[i:i+2*n+1]==pn:
            cnt += 1

print(cnt)

하지만 위 코드를 제출하면 첫 번째 서브테스크밖에 통과를 하지 못하고 50점을 받게 된다. python에서 리스트 l[a:b]의 문자열 슬라이싱의 시간복잡도는 $O(b-a)$ 라고 한다. 주어지는 S가 커질수록 시간이 오래 걸릴 수밖에 없다.

그럼 문자열 슬라이싱 말고 그냥 부분 부분 잘라서 비교를 하면 되지 않을까?

코드

n = int(input())
m = int(input())
s = input()
answer, i, count = 0, 0, 0

while i < (m - 1):
    if s[i:i+3] == 'IOI':
        i += 2
        count += 1
        if count == n:
            answer += 1
            count -= 1
    else:
        i += 1
        count = 0

print(answer)

풀이 코드를 짜보면 굉장히 간단한데, 아이디어 떠올리기가 생각보다 까다로웠던 문제인 것 같다.