문제 출처: https://www.acmicpc.net/problem/5525
처음 제출한 코드의 경우, 서브 태스크의 2번 제약 조건이 없다는 것을 제대로 이해하지 못해 50점을 맞았다.
그러다 다시 문제의 변수 범위를 각각 확인하고 어떻게하면 시간을 줄일 수 있을지 고민하다 결국 구글링을 통해 답을 얻을 수 있었다. 참고사이트는 아래 하단에 적어 두었다.
핵심은 문자열의 패턴을 N만큼의 길이로 계산하지 말고 가장 기본이 되는 패턴인 "IOI"를 검사하고 패턴의 길이를 늘려가며 N과 같을때까지 탐색하는 방법이다. 만약 전자처럼 계산할 경우 시간복잡도는 O(NM)이 되기에 시간초과가 발생한다. 후자의 경우는 O(M)만큼의 시간복잡도로 해결할 수 있다.
50점짜리
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
S = input().strip()
answer = 0
# 기본 시작은 IOI,
std = "IOI"
for i in range(N - 1): # N이 1씩 늘어날때마다 + OI를 붙여주면 됨
std += "OI"
length = len(std)
for j in range(M - length):
if std == S[j: j + length]:
answer += 1
print(answer)
100점짜리
import sys
input = sys.stdin.readline
N = int(input())
M = int(input())
S = input().strip()
count = 0
pattern = 0 # 패턴의 길이
i = 0
while i < M - 1:
if S[i: i+3] == "IOI":
i += 2
pattern += 1
if pattern == N:
count += 1
pattern -= 1
else:
i += 1
pattern = 0
print(count)
