[알고리즘] 백준 5525 파이썬 - 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=int(input())
m=int(input())
s=input()
tmp="IO"*n+'I'
a=len(tmp)
ans,i,cnt=0,0,0
#01
while i<m-1:
	#02
    if s[i:i+3]=='IOI':
        i+=2
        cnt+=1
        #03
        if cnt==n:
            ans+=1
            cnt-=1
    #04
    else:
        i+=1
        cnt=0
print(ans)

- #01 : i가 i+3까지 인덱싱 되므로, while문을 i가 m-1보다 작을 때까지만 반복하도록 한다.

- #02 : 인덱싱한 값이 'IOI'라면 i의 위치를 2 추가시켜주고 cnt를 1 늘려준다.

- #03 : 만약 cnt가 n이랑 같다면, 즉 문제에서 원한 조건을 만족했다면 ans에 1을 더해주고,

           cnt를 1 빼준다. 즉 맨 첫 번째 만족했던 s[i:i+3]을 cnt에서 1 빼준 것이다.

           그리고 바로 다음 s[i:i+3]가 'IOI'라면 또 cnt가 1 추가되어, cnt==n을 만족하여 

           ans가 1이 추가될 것이다.

- #04 : 만약 'IOI'가 아니라면 문제의 조건이 성립이 되지 않으므로,

           i는 다음 위치로 넘기고, cnt는 조건을 처음부터 이행하기 위해 0으로 해준다.

           최종적으로 구해진 ans를 출력해준다.