첫번째 풀이
50점 획득
python
import sys
input = sys.stdin.readline
n = int(input()) # n
m = int(input()) # s의 길이
s = input()
x = 2*n+1
target = []
for i in range(x):
if i % 2 == 0:
target.append("I")
else: target.append("O")
target = "".join(target)
result = 0
for i in range(m-x):
if s[i:i+x] == target:
result += 1
print(result)
두번째 풀이
O(N) 이나 O(NlogN)정도의 시간 복잡도를 가지게 설계해야한다.
단일 for문을 이용해서 구현.
python
import sys
input = sys.stdin.readline
n = int(input()) # n
m = int(input()) # s의 길이
s = input()
i, count, answer = 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)
원리
- i부터 i+3까지가 IOI면 i를 이동시킨다. count도 늘려준다.
- 다음 i ~ i+3이 IOI가 아니면 i를 1칸만 이동.
- P_N의 갯수를 세어주는 count도 초기화
- 다음 i ~ i+3 역시 IOI면 i를 2칸 이동.
- P_N의 갯수를 세어주는 count를 늘려준다.
- count가 n이 되면 answer += 1
- 이 과정을 i가 m-1이 될 때까지 반복