[ 백준 / 파이썬 ] 실버 1 - 5525. IOIOI

문제

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

• $P_1$ IOI
• $P_2$ IOIOI
• $P_3$ IOIOIOI
• $P_N$ 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	추가적인 제약 조건이 없다.

예제

풀이

일반적인 브루트 포스 방식으로는 서브태스크 1만 통과 할 수 있다.
그래서 찾아보다가 라빈카프 알고리즘을 알게 되었는데..
라빈카프 알고리즘은 해쉬값으로 서브 스트링을 찾아내는 알고리즘이었다.

예를 들어 'aaababbb' 라는 문자열에서 'abab' 가 몇 개 존재하는지 알고 싶을 때,
목표인 'abab' 의 비트값과 서브스트링의 비트값을 비교해서 같은 경우를 찾는다.

이 때 서브스트링이 'aaab' -> 'aaba' -> 'abab' 로 움직이 듯이 가장 앞에 있는 문자의 비트 값을 현재 비트 값에서 빼고 빠진 자리를 매꾸기 위해서 << 비트 연산을 해줘야하니 2를 곱해주고 거기에 다음으로 들어올 문자의 아스키 코드 값을 더해준다.

즉,

위와 같은 수식이 성립한다.

아무튼 각설하고 라빈카프 알고리즘으로 이 문제를 풀어내진 못하였다.

구글링을 통해서 이렇게 수학적 공식을 찾아내서 풀어야 했다.

참 단순한데, 왜 생각이 안날까 ...

코드

from sys import stdin

input = stdin.readline

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


def solution(N, M, S):
    answer = 0

    idx = 0
    count = 0

    while idx < len(S):
        if S[idx:idx+3] == 'IOI':
            count += 1
            idx += 2
            if count == N:
                answer += 1
                count -= 1
        else:
            idx += 1
            count = 0


    return answer


print(solution(N, M, S))