열렬히.뛰기

5525. IOIOI

알고리즘: 실전 > 5525. IOIOI

첫번째 풀이

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이 될 때까지 반복