5525번 : IOIOI - Python

문제

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

풀이(50점)

하나하나 비교하면서 처음이 같다면 그 뒤에것도 비교한다.
이렇게 풀면 50점이 나온다. 시간복잡도가 너무 커지기 때문이다.

코드(50점)

from sys import stdin

input = stdin.readline

N = int(input())
M = int(input())
P = 'I' + 'OI'*N
P = input()
count = 0



for i in range(M):
    if P[i] == P[0]: #시작이 같다면
        k = 0
        for j in range(i,i+(N*2+1)): #나머지도 같은지 비교
            if P[j]!=P[k]:
                break
            k+=1
        else: #나머지도 같다면 count+1해준다.
            count+=1

print(count)

풀이(100점)

P2에는 P1이 2개 들어있다. IOIOI = IOI+IOI(중간에 I는 겹친다고 생각해보자)
그렇다면 PN에는 P1이 N개 들어있다고 볼 수 있다.
이를 이용해서 IOI를 이용해서 IOI가 N개 있다면 PN이 있다는 식으로 풀 수 있다. 즉, IOI를 묶음으로 탐색하는 것이다.

코드(100점)

from sys import stdin

input = stdin.readline

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

cursor, count, result = 0, 0, 0

while cursor < (M - 1):
    if S[cursor:cursor + 3] == 'IOI': #IOI라면
        count += 1 #IOI의 개수를 count해준다.
        cursor += 2 #IOIOI에서 IOI를 2개있다고 보기 위해서 +2해준다.
        if count == N: # IOI가 N번 있으면 result를 증가 시킨다.. 
            result += 1
            count -= 1 #다시 IOI가 바로 뒤에 붙어있어도 되기 때문에 이를 count하기 위해서 -1해준다.

    else:#IOI가 아니라면 다시 처음부터 시작한다. cursor는 한칸 증가시킨다.
        cursor += 1
        count = 0

print(result)

참고

https://aia1235.tistory.com/30