백준 5525 - IOIOI (Python3)

코드

import sys
input = sys.stdin.readline
# I의 개수 n+1
# O의 개수 n

n = int(input())
m = int(input())
s = input()

# 최종 출력할 변수
answer = 0

# IOI가 나온 횟수를 담을 변수
cnt = 0

# 문자열의 인덱스 변수
idx = 0

while idx < (m-1):
    if s[idx:idx+3] == 'IOI':
        # 'IOI'후에 'OI'가 추가로 나오는지 보면 되니까 idx를 2 더해줌
        idx += 2
        
        cnt += 1
        if cnt == n:
            answer += 1
            
            # 'IOI'가 연속으로 'IOIOIOI' 이런 식으로 나올 경우
            # cnt가 n보다 커지는 경우가 발생
            # 이러면 이 if문이 실행되지 않는다
            # 따라서 1을 빼주고 다음 패턴을 확인한다
            cnt -= 1
    else:
        # IOI가 아니니까 cnt를 초기화
        cnt = 0
        
        # 인덱스는 1만 이동하면 됨
        idx += 1
        
print(answer)

문제 해설

참고 블로그

처음 문제를 잘못 읽고 IOI가 몇개 들어있나만 확인하면 되는 간단한 문제라고 생각해서 실패했다.

이 문제 같은 경우 시간 복잡도에 따른 부분 점수가 있다. (50점 50점)

단순 이중 for문을 이용할 시 시간 초과가 발생하여 고심을 하다가 잘 풀리지 않아 위의 참고 블로그를 참고하여 문제를 해결하였다.