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

|    서브태스크

번호배점제한

 

1	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

 

 

---

정답 코드

import sys
input = sys.stdin.readline

class Solution:
    def ioioi2(self):
        n = int(input())
        m = int(input())
        S = input().rstrip()
        res, i, cnt = 0,0,0
        
        while i < m:
            if S[i:i+3] == 'IOI':
                cnt += 1
                i += 2
                if cnt == n: # n개의 패턴을 찾은 경우
                    cnt -= 1
                    res += 1
                
            else:
                i += 1
                cnt = 0

        print(res)

if __name__ == "__main__":
    s = Solution()
    s.ioioi2()

 

 

|    비고

이 문제는 서브태스크가 있는 문제이다. n과 m이 100만 이하일 때의 조건까지 만족시켜야 100점을 받게 된다. 아래는 50점만 획득한 내 코드이다.

class Solution:
    def ioioi(self):
        n = int(input())
        m = int(input())
        S = input().rstrip()
        cnt = 0
        p = 'IO'
        pn = p * n + 'I'
        for i in range(m):
            if pn in S[i:i+2*n+1]:
                cnt += 1
        print(cnt)

처음 코드를 짰을 때는 시간복잡도가 O(M)인줄 알았다. 하지만, Python에서 문자열 슬라이싱은 시간복잡도 O(N)이 소요되기 때문에 해당 코드의 시간복잡도는 O(M*N)이 된다. 따라서 제약 조건 100만*100만 = 10^12로 1초 내 문제 풀이가 불가능했던 것이다. 정답 코드처럼 슬라이딩 윈도우 방식을 채택하면 O(M)으로 효율적인 풀이가 가능하다.