[백준/Python] 5525번 : IOIOI

문제 정보

제목 : IOIOI

번호 : 5525번

사용 언어 : Python

문제 링크

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

5525번: IOIOI

 

시간 제한	메모리 제한
1 초	256 MB

 

문제

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

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• Pₙ IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P ₙ 이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

 

입력

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

 

출력

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

 

제한

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

 

서브태스크

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

  

입출력 예제

 

---

나의 풀이

실패한 풀이

단순히 (M+1)-len(P)만큼 반복하는 for 루프를 이용해서 인덱스 i부터 i+len(P)까지 슬라이싱해 P와 비교하여 일치하면 answer을 1 증가 시키는 방법을 썼지만 태스크2에서 시간초과가 떠 50점만 나오게 되었습니다.

import sys
input = sys.stdin.readline

answer = 0
N = int(input())
M = int(input())
S = input()
P = "I" + "OI"*N

for i in range( (M+1)-len(P) ) :
    if( S[i:i+len(P)] == P ) :
        answer += 1

print(answer)

 

성공한 풀이

while을 이용해 i가 M보다 작은 동안 반복합니다. 인덱스 i부터 i+3까지 슬라이싱해 문자열 "IOI"와 같으면 i를 2증가시키고 count를 1 증가시킵니다. 만약 count가 N과 같아지면 P ₙ 와 일치하다는 의미이므로 answer을 1증가시키고 count는 1 감소시킵니다. "IOI"와 같지 않으면 아예 일치하지 않는것이므로 i는 1증가시키고 count는 0으로 변경합니다.

 

코드

import sys
input = sys.stdin.readline

answer = 0
N = int(input())
M = int(input())
S = input()

i,count = 0,0
while ( i < M ) :
    if( S[i:i+3] == 'IOI' ) :
        i += 2
        count += 1
        if count == N :
            answer += 1
            count -= 1
    else :
        i += 1
        count = 0
    
print(answer)