[백준 5525] IOIOI (python 파이썬)

[백준 5525] IOIOI (python 파이썬)
https://www.acmicpc.net/problem/5525

---

제목도 매력적이며
문제 이해도 쉽지만,
시간초과를 피하기 어려운 문제
서브데스크 문제로, 시간초과가 난다면 50점을 획득한다.

---

아이디어:
1. 슬라이딩 윈도우 사용
: 오 쉽다. 슬라이딩 윈도우 써먹어서 바로 풀어보자!
==> 시간초과 실패

2. 그럼 deque이용해서 popleft로 풀어보자
==> 시간초과 실패..
생각해보니, 슬라이딩 윈도우를 리스트 인덱싱 말고 deque로 할수 있겠는데?
구글링 해보니 deque로 하면 더욱 효율적이라고 한다.[오 약간 나 천재일지도..?][그래도 실패]

3. 진짜 생각이 안나는데 뭔가 될 거 같다
=> 커서와 패턴 이용!

---

문제풀이

1. '커서'와 '패턴'이라는 개념으로 이 문제에 접근하자.

2. '커서'를통해 리스트의 0번인덱스에서 시작, 끝까지 1회 탐색하여,
   O(N)의 시간복잡도를 가능케한다!

3. 패턴 : 미리 설정한 도달값에 도달하면 count를 1 증가신다.
   예시: 1만원을 저축해야하는 적금이 있다. 적금을 위해, 2000,5000,3000원 저축하면 적금통장+1 완성

4. 종합: 커서로 맨끝까지 탐색, count를 적립하여 문제의 조건을 충족시킨다.

while cursor < (M - 1):
    if S[cursor:cursor + 3] == 'IOI': #3칸
        count += 1
        cursor += 2
        if count == N:
            result += 1
            count -= 1
    else:
        cursor += 1
        count = 0

done!