IOIOI

04 Jun 2022 in Algorithm on 문자열

solved_ac[Class3] 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) 1 ≤ N ≤ 1,000,000 2) 2N+1 ≤ M ≤ 1,000,000 3) S는 I와 O로만 이루어져 있다.

서브태스크

예제 입력 1

1
13
OOIOIOIOIIOII

예제 출력 1

4

예제 입력 2

2
13
OOIOIOIOIIOII

예제 출력 2

2

---

---

과정 설계

문제를 풀기 전에 이미 “슬라이싱”을 사용하여 풀면 100점이 나오지 않는다는 사실을 알고 있었다.

그래서 슬라이싱을 이용하였을 때 시간복잡도가 어떻게 될까를 구해봤는데 처음에는 O(n)으로 생각하였다.

단순히 Pn만큼 문자열 길이를 순회하며 탐색하면 되는 것이니 M만큼 시간복잡도가 발생할 것이라고 생각하였는데

그래서 O(n)보다 어떻게 더 줄이지? 를 떠올리기가 어려웠다.

그러나 다시 생각해보니 Pn의 길이 N만큼 문자열 슬라이싱을 할 때도 O(n)의 시간복잡도가 발생한다는 사실을 깨달았고

문자열 슬라이싱으로 문제를 풀게되면 총 O(n^2)의 시간복잡도가 발생한다는 사실을 파악하였다.

그렇다면 시간 효율성을 높이기 위하여 어떻게 할 것인가를 고민해보았을 때 결론은 초록색 O(n)을 삭제시켜야 하였고

그러기 위해서 제일 기본 단위인 IOI를 기준으로 하여 문제를 해결하면 되겠다는 생각에 이르렀다.

Pseudo CODE

해당 스도 코드는 N=2일때 IOI를 구분점으로 하여 진행되는 예시를 보여주고 있다.

sc는 slice_count(IOI) , pc는 pn_count(Pn이 몇 번 나왔는지)를 의미한다.

CODE

import sys
input = sys.stdin.readline

# 초기 조건
n = int(input())
length = int(input())
string = input()

slice_count = 0 # IOI의 개수
pn_count = 0 # Pn의 개수

for i in range(length-2):
    if string[i] == "O":
        continue
    else:
        if string[i+1] == "O" and string[i+2] == "I":
            slice_count += 1

            if slice_count == n:
                pn_count += 1
                slice_count -= 1
        else:
            slice_count = 0

print(pn_count)