[백준] 5525 - IOIOI

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

5525번: IOIOI

문제 한줄 이해

-N이 주어질때 I가 N+1개 O가 N개가 교대로 나오는 P문자열이 있다.(P1 = IOI) 이때 S문자열에 P가 몇개 있는지 파악하기

 

생각난 풀이

1번째 방법: 배열 슬라이싱을 통해 갯수를 세보려했다.

import sys
n = int(sys.stdin.readline())
p = []
for i in range(n*2+1):
    if i % 2 == 0:
        p.append('I')
    else:
        p.append('O')


m = int(sys.stdin.readline())
s = sys.stdin.readline().rstrip()
cnt = 0
for i in range(m-(2*n+1)+1):
    if p == s[i:i+2*n+1]:
        cnt +=1
print(cnt)

간단하네 하고 제출을 했지만 시간초과가 발생했고 슬라이싱은 O(b-a)의 시간복잡도를 가지고 있다는 것을 알게됐다...

 

2번째 방법:  슬라이싱을 최대한 줄여보는 방법을 고민해봤지만 떠오르지 않았고 검색을 통해 힌트를 얻을 수 있었다. 

패턴을 활용해 슬라이싱 범위를 고정하고, 조건에 맞지 않으면 이미 확인한 부분들은 뛰어 넘는것이다.

import sys
n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
s = sys.stdin.readline().rstrip()

start,end,cnt = 0,0,0

while end < m:
    # 슬라이싱을 쓰지만 범위를 늘리지않고 일정하게 유지하면서 시간단축
    # 패턴이 IOI, IOIOI...이므로 end:end+3이 IOI에 만족하면 end +=2
    if s[end:end+3] == "IOI":
        end += 2
        # 길이가 문제에서 제시한 길이와 동일하면 cnt를 +1해주고
        # start위치를 +2 시킨다 why? IOIOI라면 다음위치는 당연히 O일테고 다음 I로 가야하기 때문
        if end - start == 2*n:
            cnt +=1
            start +=2
    # 패턴에 맞지 않으면 그동안 확인한 부분들은 바로 뛰어넘어야하므로 start와 end위치를 end+1로 조정
    else:
        start = end+1
        end = end +1
print(cnt)