문제

제한 사항 및 예제

풀이

풀이 1(시간 초과)

처음 접근시에는 리스트 슬라이싱을 활용해 $P_N$과 일치하는 부분을 찾으면 count를 올리는 식으로 구현하였다.

# IOIOI
n = int(input())
m = int(input())
s = input()
# p = ('O').join(['I']*(n+1))
# p와 일치하는지 확인
cnt=0
for i,v in enumerate(s):
    if v=='I':
        if i+(2*n+1)<m:
            if s[i:i+(2*n+1)]==p:
                cnt+=1
print(cnt)

하지만 $m=1,000,000$이고 IOIOIO...의 식으로 계속 반복되는 경우라고 하면, 슬라이싱을 사용해야하는 횟수가 500,000-1=499,999이므로 n이 21만 되어도 천만의 연산 횟수를 넘는다.

그러므로, 슬라이싱을 최소화 하는 방법을 적용해야 한다.

풀이 2(성공)

문자가 규칙에 맞게 배열되는 동안 수를 1씩 올려나가면 다음과 같은 배열이 만들어진다.

OOIOIOIOIIOII -> 0012345671231

그리고 이 중에서 $P_N$의 길이와 같은 $2N+1$보다 크거나 같고, 홀수인 경우를 선택하면 조건에 만족하는 부분이 선택된다.

# IOIOI
n = int(input())
m = int(input())
s = input()
# 슬라이싱 없이
cnt_lst = [0]*m
for i,v in enumerate(s):
    if v=='I':
        if cnt_lst[i-1]:
            if s[i-1]=='O':
                cnt_lst[i]=cnt_lst[i-1]+1    
            else:
                cnt_lst[i]=1
        else:
            cnt_lst[i]=1
    else:
        if cnt_lst[i-1]:
            if s[i-1]=='I':
                cnt_lst[i]=cnt_lst[i-1]+1

for i in cnt_lst:
    if (i>=2*n+1)&(i%2==1):
        cnt+=1

print(cnt)

다른 풀이

IOI의 단위로 count를 올려서 N만큼 count가 되면 결과값을 하나씩 올리고, count를 하나 줄이고 다시 탐색을 반복해 나가는 알고리즘이다.

나의 풀이와 방식은 조금 다르지만, 비슷한 원리로 해결하는 것 같다.

N = int(input())
M = int(input())
S = input()

cursor, count, result = 0, 0, 0

while cursor < (M - 1):
    if S[cursor:cursor + 3] == 'IOI': #3칸
        count += 1
        cursor += 2
        if count == N:
            result += 1
            count -= 1
    else:
        cursor += 1
        count = 0

print(result)