백준 IOIOI 5525 (파이썬)

실버, 문자열

 

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

 

문제

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이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 PN이 몇 군데 포함되어 있는지 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

서브태스크

번호	배점	제한
1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

 

 

제출 코드 (정답) 

N, M = int(input()), int(input())
S = input()
p = "I"+"OI" * N
i = 0
pattern = 0
cnt = 0
while i < M-2:
    if S[i:i+3] == "IOI":
        pattern += 1
        if pattern == N:
            pattern -= 1
            cnt += 1
        i += 1
    else:
        pattern = 0
    i += 1
print(cnt)

 

IOI 패턴이 연속으로 N번 나오는지 체크하여 IOI 패턴이 연속으로 N번  나오면 pattern을 -1 만 해주고 인덱스를 2 증가  

만약 한번이라도 IOI 패턴에서 어긋나면 pattern 모두 초기화 후 인덱스를 1 증가

핵심은 항상 인덱스를 +1 해주어서 지나왔던 인덱스를 다시 탐색하지 않는 것이 핵심 

O(M) 시간복잡도 가짐