[BOJ][⚪1][백준#05525] IOIOI

문제 출처

BAEKJOON Online Judge #5525

문제

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로만 이루어져 있다.

예제

예제 1

입력

1
13
OOIOIOIOIIOII

출력

4

예제 2

입력

2
13
OOIOIOIOIIOII

출력

2

My Sol

import sys
input = sys.stdin.readline

N = int(input())
L = int(input())
txt = list(map(lambda x: (0 if x=='O' else 1), input()))

k = 0
check = 1
cnt = 0
l = 0
while k < L:
    flag = 0
    # 시작
    if txt[k] == check:
        while k < L and txt[k]==check:
            check ^= 1
            l += 1
            k += 1
            flag = 1

        if l >= 2*N+1:
            cnt += (l-(2*N-1))>>1
        l = 1 if k<L and txt[k] else 0
    k = k if flag else k+1

print(cnt)

I와 O가 교차해서 반복되는 경우에만 그 안에서 문자열을 찾을 수 있는데, 이때 N이 1이고 I와 O의 반복 길이가 7이면 길이 3의 단위가 2칸씩 이동하는 것이고, N이 1씩 커질수록 그 카운트가 1씩 줄어든다. 이를 이용해 반복 길이 l이 2*N+1보다 크거나 같은 경우 cnt를 해줄 수 있고, 이 cnt는 N의 크기를 고려하여 계산해줄 수 있다. 이 누적 카운트를 나중에 출력하는 것이고, 만약 교차하는 반복이 끊겼다면 0의 연속 또는 1의 연속으로 반복이 끊겼을텐데, 이 각각의 상황에 따라 l의 시작값을 달리 하여 다음 탐색 값에서 이어서 시작할 수 있도록 하였다.

결과

맞았습니다!!

모범답안

출처

N = int(input())
M = int(input())
P = "I"+"OI"*N
S = input()

pattern = 0
result = 0
i = 0
while i < M-2:
  if S[i] == 'I' and S[i+1] == 'O' and S[i+2] == 'I':
    pattern += 1
    i+=1
  else:
    pattern = 0
  if pattern >= N:
    result += 1
  i+=1
print(result)

연산시간과 코드 길이가 짧은 풀이를 찾아 분석해보았다. 이 분은 IOI 단위를 찾아 2칸씩 밀어가며 IOI라면 pattern을 1씩 늘리는데, pattern의 수가 N개가 되는 순간이 가능한 배치의 시작인 것이다. 그 이후에도 IOI가 더 붙는다면 가능한 배치가 하나씩 늘어나는 점에서 착안한다. 만약 IOI가 깨진다면 pattern을 0으로 초기화하면, 다시 N을 충족하는 pattern이 될 때까지 반복을 확인한다. i는 0부터 시작하여 1칸 단위로 시작점을 이동하므로 모든 점으로부터 IOI를 파악할 수 있다. 간결하면서도 똑똑한 해결법이었다.