[백준] 6064번 IOIOI [Python] - 문자열

N+1 개의 I 사이에 N개의 O가 들어있는 문자열

$P_N$ : IOIOIOIO...IOI에 대해서 N이 주어질 때

 

I와 O로만 이루어진 길이가 M인 문자열에서 $P_N$이 몇 번 포함되는지 세는 문제

IOIOIOI에는 IOI가 3번 포함됨.

 

문제

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안에 PN이 몇 군데 포함되어 있는지 구하는 프로그램을 작성하시오.

입력

첫째 줄에 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	추가적인 제약 조건이 없다.

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

 

N과 M이 작은 수 일 때,

문자열 s를 처음부터  끝까지 $P_N$의 길이만큼 슬라이싱 해서 확인하는 코드

import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
s = sys.stdin.readline()
P_N, c = 'IO'*N+'I', 0
N *= 2
for i in range(M-N):
    if s[i:i+N+1] == P_N:
        c += 1
print(c)

 

N과 M이 커지면,

슬라이싱 해서 $P_1$을 이어서 n번 찾아서 개수를 세는 방식으로 접근

n번이 안되면 이후 문자열에 대해서 다시 $P_1$카운팅하고,

n번 이상 발견되면 $P_N의 개수를 세고, 그 때부터 끊기지 않고 $P_1$이 발견되면 개수를 더 세준다.

import sys
N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
s = sys.stdin.readline()
i, c, t = 0, 0, 0
while i < M-2:
    if s[i:i+3] == 'IOI':
        t += 1
        i += 2
        if t == N:
            c += 1
            t -= 1
    else:
        i += 1
        t = 0
print(c)

 

 

아래 코드는 find 매소드를 통해 첫 코드처럼 찾고자하는 문자열의 시작 index를 가져와 사용했고,

두번째 코드 처럼 이어지는 $P_1$ 의 개수 만큼 $P_N$의 개수를 더했습니다.

import sys
def f(s, i, c):
    while True:     		# 찾으려는 문자열이 존재할 때, 그 뒤에 "OI"가 붙어 있으면
        if s[i:i+2] == 'OI':
            c += 1  		# 개수를 더 세고
            i += 2  		# 두 글자를 세기 때문에 index는 2씩 증가
        else:
            return i-2, c+1 	# 2 증가 시킨 index는 다시 2를 낮추고, 개수와 함께 반환
        
def main():
    N = int(sys.stdin.readline())
    _ = int(sys.stdin.readline())
    s = sys.stdin.readline()
    P_N = 'IO'*N+'I'   	 	# 찾고자하는 문자열
    c = 0
    while True:
        i = s.find(P_N) 	# 주어진 문자열에서 찾고자 하는 문자열이 발견되는 시작 인덱스
        if i == -1: break   	# 존재하지 않으면 인덱스 대신 -1이 반환됨 >> 탐색 종료
        
        # 존재하는 경우, 이후 "OI"가 붙어있으면 그만큼 개수를 더 추가하는 함수 실행
        i, c = f(s, i+2*N+1, c)   
        s = s[i:]  		 # 개수를 다 센 문자열은 제거 후 다시 탐색 시작
    print(c)

if __name__=="__main__":
    main()

 

예제 입력 1 

1
13
OOIOIOIOIIOII

예제 출력 1 

4

• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII
• OOIOIOIOIIOII

 

예제 입력 2 

2
13
OOIOIOIOIIOII

예제 출력 2 

2

• OOIOIOIOIIOII
• OOIOIOIOIIOII