백준 5525번 IOIOI [Python]

[Silver I] IOIOI - 5525

문제 링크

성능 요약

메모리: 34404 KB, 시간: 348 ms

분류

문자열

제출 일자

2024년 4월 30일 14:39:04

문제 설명

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

• P₁ IOI
• P₂ IOIOI
• P₃ IOIOIOI
• P_N IOIOI...OI (O가 N개)

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

입력

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

출력

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

서브태스크

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

풀이

# 서브태스크 조건 하나만 부합하는 코드
import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
IOI = 'I'+('OI'*N)
S = input().rstrip()

i,cnt = 0,0
while True:
    if i > M-len(IOI):
        break
    if S[i] == 'I' and IOI == S[i:i+len(IOI)]:
        cnt += 1
    i += 1
print(cnt)

처음에 작성한 코드이다. while문으로 인덱스 i의 값을 하나씩 증가해주면서 첫글자가 I이고, P_N인 값을 찾았을 때 cnt를 증가해주는 흐름이다.

이렇게 했을때는 만족하는 서브태스크가 1개이므로 2개 다 만족하기 위해서는 N과 M이 1,000,000 이하의 범위일 경우에 시간복잡도를 고려하여 코드를 수정했다. 처음 코드는 인덱스 i를 1씩 증가해주면서 IOI패턴을 탐색하기 때문에 시간이 오래걸린다. 따라서 N에 따른 IOI의 개수를 측정해서 그 개수가 N과 같을 때 P_N의 개수를 증가해주는 방식으로 구현했다.

i,cnt,res = 0,0,0
while i < M:
    if S[i:i+3] == 'IOI': # 'IOI' 문자열을 찾았을 때
        i += 2 # IOI에서 두번째 I 위치로 이동
        cnt += 1 # N을 찾기위한 cnt 증가
        if cnt == N: # P_N 조건과 같으면
            cnt -= 1 # <설명 참고>
            res += 1 # P_N 개수 증가
    else: # 'IOI'문자열이 아니면
        cnt = 0 # cnt 초기화
        i += 1 # 인덱스 +1 증가

IOI패턴을 찾았을 경우에는 인덱스를 1이 아닌 2를 증가해서 다음 I부터 탐색할 수 있도록 한다. cnt와 N이 같을 경우에 cnt-1을 해주는 이유는 이후에 연속된 IOI패턴이 있을 경우에 카운트해주기 위해서이다. 아래 그림은 백준 사이트의 예제 2번을 애니메이션으로 나타낸 것이다.

9번째 인덱스에서 IOI를 찾고 이후 IOI가 연속돼있지 않으므로 cnt는 다시 0으로 초기화되는 것을 확인할 수 있다.

전체 코드

import sys
input = sys.stdin.readline

N = int(input())
M = int(input())
IOI = 'I'+('OI'*N)
S = input().rstrip()

i,cnt,res = 0,0,0
while i < M:
    if S[i:i+3] == 'IOI':
        i += 2
        cnt += 1
        if cnt == N:
            cnt -= 1
            res += 1
    else:
        cnt = 0
        i += 1
print(res)