[백준] 5525번: IOI

💻 백준 5525번: IOI

문제 링크:(https://www.acmicpc.net/problem/5525)
알고리즘 분류: 문자열

문제 소개 🧐

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초, 256MB

첫 번째 시도: 단순 비교 👊

Idea

Pn을 구하고 S를 슬라이싱해서 돌며 Pn이 몇 개 있는지 단순히 비교하며 구한다.

Code

import sys

N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()

pattern = 'IOI'
for i in range(N-1):
    pattern += 'OI'

cnt = 0
for i in range((M-2*N-1)):
    if S[i:i+2*N+1] == pattern:
        cnt += 1

print(cnt)

Result

34% 실패

두 번째 시도: 슬라이싱 범위 수정 🔍

Idea

마지막 끝부분의 문자를 세지 못하고 있었다.

Code

import sys

N = int(sys.stdin.readline().rstrip())
M = int(sys.stdin.readline().rstrip())
S = sys.stdin.readline().rstrip()

pattern = 'IOI'
for i in range(N-1):
    pattern += 'OI'

cnt = 0
for i in range((M-len(pattern))+1):
    if S[i:i+len(pattern)] == pattern:
        cnt += 1

print(cnt)

Result

부분 통과

슬라이싱 된 S와 pattern을 비교하는 과정이 for문 안에서 이뤄지므로 시간 복잡도가 O(N^2)이 되어버리는듯 하다.

세 번째 시도: O(N)으로 최적화 ✨

Idea

S를 한번만 순회하는 방법을 생각해야한다.

인덱스를 이용해 직접 접근하는 방법밖에 없다고 판단.

Code

import sys

N = int(sys.stdin.readline())
M = int(sys.stdin.readline())
S = sys.stdin.readline().strip()

ans = 0
cnt = 0
idx = 1
while idx < M - 1:
    if S[idx-1] == 'I' and S[idx] == 'O' and S[idx+1] == 'I':
        cnt += 1
        if cnt == N:
            cnt -= 1  # 다음 i에서 또 패턴이 맞으면 바로 ans += 1 이 되도록   
            ans += 1
        idx += 1
    else:
        cnt = 0  # 패턴이 깨지면 바로 0부터 시작
    
    idx += 1

print(ans)

Result

성공 🎉

개선할 부분 🤔

시간이 중요해질수록 직접 인덱스를 이용해 접근하는 것이 더 최적화할 수 있는 방법이라는 것을 유의해야겠다.