BOJ-5525 IOIOI

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

문제 소개

N + 1개의 I와 N개의 O로 이루어진, I와 O가 교대로 나오는 문자열을 $P_N$이라고 한다.

ex) $P_2$ = IOIOI

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 $P_N$이 몇 군데 포함되어 있는지 구한다.

문제 풀이

먼저 찾고자 하는 문자열과 그 길이를 계산하여 각각을 변수에 저장한다. 아래 코드에서는 t와 lengh가 그것이다. 변수 cnt는 $P_N$이 발견된 횟수이다.

문자열이 존재하는지 검사하기 위해 주어진 문자열 s를 인덱스 0부터 탐색하게 되며, (s의 길이 - length + 1)까지만 탐색해도 문자열의 끝까지 검사가 가능하다.

$P_N$은 길이에 상관없이 무조건 I로 시작되므로, s[i]가 I인 경우에만 해당 인덱스로부터 length뒤 까지의 문자열(s[i:i + length])이 $P_N$인지 검사하고 그 외에는 인덱스를 1 증가시킨다.

만약 $P_N$을 찾았다면 cnt를 1 증가시키고 찾은 $P_N$뒤에 “OI”가 있는지 다시 검사한다. 즉, s[i + 2:i + length + 2] 또한 $P_N$인지 다시 검사한다. 이 작업은 $P_N$뒤에 “OI”가 등장하지 않을 때까지 계속 반복한다.

위 반복 작업은 한번 할 때마다 cnt를 1증가시키고 인덱스를 “OI”의 길이인 2증가시킨다.

일련의 하나 또는 연속된 $P_N$의 검사가 끝났다면 인덱스를 length만큼 증가시킨다. (현재 인덱스 + $P_N$의 길이) 이후부터 다시 탐색해야하기 때문이다.

마지막으로 누적된 cnt를 출력한다.

인덱스를 임의로 조절하기 위해 for 문이 아닌 while문을 사용하였다.

코드

from sys import stdin
input = lambda: stdin.readline().rstrip()

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

# 변수 선언
t = "IO" * n + "I"
length = 2 * n + 1
cnt = 0

i = 0
while i < len(s) - length + 1:
    # I로 시작하는 경우에만 검사
    if s[i] == "I":
        # P_N을 발견한 경우
        if s[i:i + length] == t:
            cnt += 1
            # 이어지는 또 다른 P_N이 있는지 검사
            while s[i + length:i + length + 2] == "OI":
                cnt += 1
                i += 2
            i += length
        else:
            i += 1
    else:
        i += 1
        continue

print(cnt)