[백준] 5525 IOIOI - 파이썬

문제

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

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이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

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

제한

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

 

 

---

풀이

 

서브태스크(효율성 체크)가 있는 문제였다.

O(1)로 풀 수 있는 문제다.

 

입력받은 문자열 S를 순회하며 I와 O가 번갈아 나온다면 큐에 넣으며 N을 카운트한다.

만약 같은 문자가 나온다면 ex) II, OO 더이상 P(N)문자열이 아니므로 큐를 초기화하고 정답을 업데이트한다.

이 때 cnt - n +1을 정답에 더해준다. P(cnt)문자열 안에 n만큼의 문자열이 몇 개 있는지 계산하는 과정이다.

 

모든 문자를 순회하고 나서 마지막에 큐에 있는 P(cnt)를 계산해주지 않았어서 틀렸었다.

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
s = list(input()[:-1])

q = []
cnt = 0
answer = 0
for si in s:
    if not q:
        if si == 'I':
            q.append(si)
    elif q[-1] == si:
        if cnt >= n:
            answer += (cnt-n+1)
        cnt = 0
        q.clear()
        if si == 'I':
            q.append(si)
    else:
        q.append(si)
        if si == 'I':
            cnt += 1
if cnt >= n:
    answer += (cnt-n+1)
print(answer)