TIL 코딩공장

백준 파이썬 공부 2025.02.28
5525번 IOIOI (실버 1)

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

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

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

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

5. 문제 풀이
처음에는 단순한 슬라이딩 윈도우 방식으로 문제를 풀이해보았다.

>> 코드 1. 슬라이딩 윈도우 방식, 50점

def checkin(idx):
    for i in range(length):
        if i%2 == 0:
            if s[idx+i] == 'I':
                continue
            else:
                return False
        else:
            if s[idx+i] == 'O':
                continue
            else:
                return False
    return True

n = int(input())
m = int(input())
s = list(input())
length = 2*n+1

cnt = 0
for i in range(m-length+1):
    if s[i] == 'I':
        if checkin(i) == True:
            cnt += 1
        
print(cnt)

단순한 슬라이딩 윈도우 방식으로는 너무 큰 숫자의 n과 m을 감당하지 못하는 듯 하다

나는 'I' 가 나올 때마다 Pn이 존재하는지 검사를 시행했는데,
이러면 시간 복잡도가 (I의 개수) * O(n)이 되므로, 다른 방식을 사용해야헀다.

다행히 검사해야하는 패턴이 "OI"의 반복이라고 볼 수 있기 때문에,
I로 시작해서 이후에 "OI" 가 몇번 반복되는지 알면 해당 위치에 Pn이 몇개있는지 알 수 있다.

예를 들어 P4을 찾는 상황에, 해당 위치에서 탐색을 시행했을 때
"OI"가 8번 존재한다면, 해당 위치에는 P4가 8-4+1 = 5개 존재한다는 것을 알 수 있다.

IOIOIOIOIOIOIOIOI >> IOIOIOIOI OI OI OI OI >> IOIOIOIOI 5개 존재

그리고 이렇게 구간의 Pn 개수를 탐색 후 구간 이후로 넘어가 
또 패턴이 존재하는 구간이 나오면 계산하기를 반복하여 총 개수를 구하면 된다.

>>>코드 2. 슬라이딩 윈도우 + 카운팅 

import sys

n = int(sys.stdin.readline())
m = int(sys.stdin.readline())
s = sys.stdin.readline().strip()

length = 2*n+1
cnt, idx = 0, 0
while idx < m - 1:
    if s[idx] == 'I':
        pattern = 0
        while True:
            if idx + 2 < m and s[idx+1] == 'O' and s[idx+2] == 'I':
                pattern += 1
                idx += 2
            else:
                if pattern >= n:
                    cnt += (pattern - n + 1)
                idx += 1
                break
    else:
        idx += 1

print(cnt)

6. 문제 링크
https://www.acmicpc.net/problem/5525