백준 #5525 IOIOI

문제 링크

[5525 IOIOI]

문제 설명

IOI, IOIOI, IOIOIOI … 등의 패턴이 문자열에 몇개 있는지 찾는 문제

코드

import sys
input = sys.stdin.readline


N = int(input())
M = int(input())
S = list(input().rstrip())

cnt = 0
cur = []
cur_len = 0
for i in range(M):
    cur.append(S[i])
    cur_len += 1
    if cur[0] == "O":
        cur = []
        cur_len = 0
        continue
    if cur_len >= 2:
        if cur[-2] == cur[-1]:
            if cur[-1] == "I":
                cur = ["I"]
                cur_len = 1
            else:
                cur = []
                cur_len = 0
        else:
            if cur_len == (2 * N + 1):
                cnt += 1
                cur = ["I"]
                cur_len -= 2
print(cnt)

풀이

이 문제는 예전부터 몇 번 봤던 문제인데 좀 복잡해보여서 겁먹어가지고 계속 미루다가 이번에 풀어보자! 해서 풀었다 ㅎ 핵심은 코드 맨 아래부분이다. 문자열을 계속 업데이트 해주는데 전체 문자열을 데리고 다니는게 아니라 길이만 계속 트래킹해주면 된다. 전체 문자열을 계속 데리고 다닐 경우 시간초과가 발생하게 된다!!