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

---

1. 코드

"""
ex) 
        ==input==
2
13
OOIOIIOIOIOIOIOIOIOIOOIOI
            
        ==1. 문자열 Pi 를 만들 수 있는 단위로 끊어서 parsing 리스트에 문자열의 길이만 저장==
            OO IOI IOIOIOIOIOIOIOI OO IOI
​
            list 로 표현한 예시
            -> [
                ['I', 'O', 'I'],
                ['I', 'O', 'I', 'O', 'I', 'O', 'I', 'O', 'I', 'O', 'I', 'O', 'I', 'O', 'I'],
                ['I', 'O', 'I']
                ]
​
            리스트 사용은 시간복잡도 공간복잡도 낭비이므로 stack 의 길이만 저장
            parsing = [3, 15, 3]
​
        ==2. parsing 값들을 Pi 으로 변환 후, Pn이 몇 개 들어갈 수 있는지 계산==
            공식들은 P1,P2,P3,P4.. 그려보면 자연스럽게 알 수 있음
​
            - 변환 공식: (p - 1) // 2
            [3, 15, 3] -> [P1, P7, P1]
​
            - Pn이 몇 개 들어갈 수 있는지 확인하는 공식: Pi - Pn + 1
            P1 -> P2가 들어갈 수 없으므로 무시
            P7 -> P2가 6번 들어갈 수 있음
            P1 -> P2가 들어갈 수 없으므로 무시
        answer = 6
"""
​
n = int(input())
m = int(input())
answer = 0
chars = input()
parsing = []
stack = []
"==1=="
for char in chars:
    if not stack and char == 'O':
        continue
    """
        line 54: 'I', 'IO' 는 parsing 에 추가되지 못하도록 설정
        line 56: stack 끝이 I  -> len(stack) 그대로 추가        ex) IOIOIOI -> IOIOIOI
        line 65: stack 끝이 O  -> len(stack)-1 을 추가         ex) IOIOIOIO -> IOIOIOI
    """
    if char == 'I':
        if not stack:
            stack.append(char)
        elif stack[-1] == 'O':
            stack.append(char)
        else:
            if len(stack) > 2:  
                parsing.append(len(stack))
            stack.clear()
            stack.append(char)
    elif char == 'O':
        if stack[-1] == 'I':
            stack.append(char)
        else:
            if len(stack) > 2:
                parsing.append(len(stack) - 1)
            stack.clear()
""" 마지막 stack 은 파싱될 수 있는 조건이 없으므로 따로 확인"""
if len(stack) > 2:
    if stack[-1] == 'O':
        parsing.append(len(stack) - 1)
    elif stack[-1] == 'I':
        parsing.append(len(stack))
"==2=="
for p in parsing:
    o = (p - 1) // 2
    if o >= n:
        answer += o - n + 1
print(answer)

---

2. 후기

stack 문제처럼 앞에서부터 한 문자씩 읽어들인다는 관점으로 풀었다다. 기존 문자열에 새로 읽어들인 문자열이 추가됐을 때 발생할 수 있는 케이스들을 조건문으로 구현했다.