[백준] 5525번 IOIOI

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

5525번: IOIOI

 

문제

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

 

 

풀이

실제로 P와 S를 구현해서 0번부터 탐색하면서 체크하였다.

N = int(input())
M = int(input())
S = input()
P = 'IO'*N + 'I'
answer = 0

for i in range(M - len(P)+1):
    if S[i] == 'I':
        if S[i:i+len(P)] == P:
            answer += 1
print(answer)

이 경우 서브테스크 1은 Input의 길이가 짧기 때문에 100 * 10000으로 통과할 수 있지만
서브테스크 2는 1000000 * 1000000이기 때문에 통과할 수 없다.

서브테스크 2를 통과하기 위해서는 O(N) 이나 O(NlogN)정도의 시간 복잡도를 가지게 설계해야한다.
그럼 단일 for문을 이용해서 구현해야하는데 문자열이 규칙이 존재하기 때문에 단순 비교가 아니라 연산을 통해서 문자열을 찾아야한다.

 

전체 코드

N = int(input())
M = int(input())
S = input()
answer, i, count = 0, 0, 0

while i < (M - 1):
    if S[i:i+3] == 'IOI':
        i += 2
        count += 1
        if count == N:
            answer += 1
            count -= 1
    else:
        i += 1
        count = 0

print(answer)

IOI가 몇 번 연속되는지 갯수만 찾아서 체크하게 되면 N * 3 정도의 시간으로 문제를 풀 수 있게 된다.

IOI가 발견되면 index를 2개 이동시키고 아닌 경우에는 index를 1개 이동 시키면서 검사한다.