[Python] 백준 - 5525번 : IOIOI

https://www.acmicpc.net/problem/5525

5525번: IOIOI

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 PN이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

 

서브테스크 문제로 처음 내가 생각한 해결법으로는 50점을 받았다

처음에는 투포인터로 각 길이만큼 확인하려했고, 두번째로는 pattern을 지정해주어 확인해주는 방식으로 하였다.

하지만 위 해결법들로는 시간 복잡도 내 해결이 불가능했다.

 

시간복잡도 내 해결하는 방법은

"IOI"라는 문자열을 하나의 Pattern으로 두어 인덱스 1부터 시작해서 s[i-1], s[i], s[i+1]이 위 패턴과 일치하는지 확인한다. 만약 일치하면 패턴의 개수를 세어주는 변수를 +1 해주고 패턴의 개수가 N개가 되면 P(n)에 부합하는 문자열이 된다. 그러므로 정답을 체크해주고 패턴은 다시 -1해준다. 이렇게 되면 O(m)의 시간복잡도로 문제를 해결할 수 있다

 

import sys
import re

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
S = sys.stdin.readline()

cnt = 0
pattern = 0
i = 1

while i < M-1:
    if S[i-1] == 'I' and S[i] == 'O' and S[i+1] == 'I':
        pattern += 1
        if pattern == N:
            pattern -= 1
            cnt += 1
        i += 1
    else:
        pattern = 0
    i += 1
print(cnt)