[🥈2 / 백준 5525 / 파이썬] IOIOI

 

5525번: IOIOI

 

문제

N+1개의 I와 N개의 O로 이루어져 있으면, I와 O이 교대로 나오는 문자열을 P_N이라고 한다.

• P1 IOI
• P2 IOIOI
• P3 IOIOIOI
• PN IOIOI...OI (O가 N개)

I와 O로만 이루어진 문자열 S와 정수 N이 주어졌을 때, S안에 P_N이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N이 주어진다. 둘째 줄에는 S의 길이 M이 주어지며, 셋째 줄에 S가 주어진다.

출력

S에 P_N이 몇 군데 포함되어 있는지 출력한다.

제한

• 1 ≤ N ≤ 1,000,000
• 2N+1 ≤ M ≤ 1,000,000
• S는 I와 O로만 이루어져 있다.

서브태스크

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

 

예제 입력 1 1 13 OOIOIOIOIIOII

예제 출력 1 4

 

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

 

예제 입력 2 2 13 OOIOIOIOIIOII

예제 출력 2 2

 

• OOIOIOIOIIOII
• OOIOIOIOIIOII

 

풀이

 

특정 문자열에 패턴이 몇 번 나오는지 세어 출력하는 문제이다.

패턴의 길이가 p라고 할 때, 브루트 포스로 인덱스 0부터 M-p 까지 순환하며 패턴을 일일이 확인한다면 시간 초과가 발생할 것이다.

 

이 문제를 해결하기 위해 다양한 알고리즘이 사용될 수도 있겠지만, 필자는 문자열 S를 딱 한 번만 돌며 반복되는 OI를 구하기로 했다.

예제 2을 예로 들겠다.

 

• OOIOIOIOIIOII

인덱스 2~6 위치에서 패턴이 발견되었다.

그렇다면 그 다음 패턴을 찾는 방법은 다시 인덱스 3부터 패턴을 대조해보는 것이 아닌, 그 뒤의 OI 두개만 확인하면 되는 것이다.

만약, OI가 순서대로 오지 않고 패턴에 어긋난다면 그 위치부터 다시 패턴 대조를 시작한다.

 

import sys
input = sys.stdin.readline
sys.stdin = open("pyt.txt","r")

def main():
    n = int(input())
    m = int(input())
    s = input().rstrip()

    ans,cor = 0,1
    start = False
    OI,OIb = ["O","I"],False
    for i in range(m):
        # 모든 패턴은 I부터 시작하므로, 대조중이 아닐 때 마주친 글자가 I이라면 대조를 시작한다.
        if start == False and s[i] == "I":
            start = True
            OIb = False
            continue

        if start:
            if s[i] == OI[OIb]:
                if OIb == True:
                    cor += 1

                OIb = not OIb
                continue
            else:
                if s[i] == "O":
                    start = False
                    
        # 대조 종료이므로 결과 더하기
        ans += max(0,cor-n)
        OIb = False
        cor = 1

    ans += max(0,cor-n)
    print(ans)
    
if __name__ == "__main__":
    main()