처음보는 유형 (#5525번 IOIOI)

#5525번 IOIOI https://www.acmicpc.net/problem/5525

5525번: IOIOI

 

일단 풀었다.

 

50점 짜리 코드

from sys import stdin
input = stdin.readline
p = "IOI" + "OI"*(int(input())-1)
l = len(p)
t = int(input())
target = input().strip()
answer = 0
for i in range(t):
    if target[i:i+l] == p:
        # print(target[i:i+l])
        answer += 1

print(answer)

 

난생 처음보는 50점이 나왔다.

 

당황스러웠다.

 

아무튼 원인은 시간초과였는데 다음과 같이 바꿔야만 시간초과를 피할 수 있다.

 

정답 코드

from sys import stdin
input = stdin.readline
n = int(input())
m = int(input())
s = input().strip()

answer = 0
pattern = 0
i = 0

while i < m-2:
    if s[i] == "I" and s[i+1] == "O" and s[i+2] == "I":
        pattern += 1
        if pattern == n:
            answer += 1
            pattern -= 1
        i += 2
    else:
        pattern = 0
        i += 1

print(answer)

두 코드의 차이는 i를 기준으로 순환을 할 때, 패턴을 찾은 순간 패턴의 길이 만큼 넘어갈 수 있는지의 여부인 듯 하다.

 

매 인덱스에서 패턴을 찾는 첫 번째 코드보다는

 

한 인덱스에서 +2까지의 패턴을 찾은 뒤 i+2를 진행해 2개의 인덱스를 넘어가기 때문에

시간초과에 걸리지 않는 듯 하다.

 

떠올리지 못해 아쉽지만

 

그래도 난 나를 응원한다.