백준 5525: IOIOI - 문자열(파이썬)

IOIOI 성공서브태스크다국어

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

입력

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

출력

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

제한

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

 

 

 

내 코드

import sys

n=int(sys.stdin.readline())
m=int(sys.stdin.readline())

arr=sys.stdin.readline().rstrip()

start=0
end=3

answer=0
cnt=0
while end<=m: #end는 m까지 가능. (arr[x:y]에서 arr[y-1]까지 들어가므로)
    if arr[start:end]=='IOI':
        cnt+=1
        start+=2 #start 2칸 전진
        end+=2 #end 2칸 전진
        if cnt==n: #IOI 개수가 우리가 원하는 개수면,
            answer+=1 #정답을 ++;
            cnt-=1 #누적한 IOI 개수를 --;
        continue
    cnt=0 #연속되는 IOI가 끊기면 cnt=0;
    start+=1 #start 1칸 전진
    end+=1 #end 1칸 전진

print(answer)

 

 

풀이 및 접근)

- 하나하나 일일이 비교하면 시간 초과가 난다.

- 시간을 줄이는 방법은, 제일 기본적인 단위인 "IOI"의 개수를 카운트 하는 방법으로 문제를 푸는 것이다.

- 탐색구간의 길이를 3으로 고정하고 이 구간을 문자열 내에서 전진시키며 확인한다. "IOI"를 만나면 cnt++를 해주고 start와 end를 두칸 전진한다. 왜냐하면 다음의 "IOI"는 두칸 뒤부터 존재 가능하기 때문이다. "IOI"를 만나지 않으면, cnt=0 해주고 startd와 end를 한칸 전진한다.

- 이러한 과정에서 cnt가 우리가 원하는 n이 되면 답에 +1를 해준다.