[문제 풀이] 백준 5525

해결 과정

역시 시간복잡도 고려 문제. O(n^2)을 줄이는 방법은 순차대로 1번씩만 돌 수 있는지 여부. 다른 풀이도 참고했다.

 

나의 풀이

N = int(input())
M = int(input())
S = input()

pn = "IO" * N + "I"
pnNum = len(pn)

cur = 0
answer = 0
count = 0
while cur < M -1:
    if S[cur:cur+3] == "IOI":
        cur += 2
        count += 1
        if count == N:
            answer += 1
            count -= 1
    else:
        cur += 1
        count = 0

print(answer)

 

첫 풀이 (50점)

N = int(input())
M = int(input())
S = input()

pn = "IO" * N + "I"
pnNum = len(pn)

answer = 0
for i in range(M-pnNum+1):
    if S[i] == "I" and S[i:i+pnNum] == pn:
        answer += 1

print(answer)

 

다른 풀이

 

 

IDEA