[백준/파이썬]5525 IOIOI

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

5525번: IOIOI

 

백준 5525 IOIOI채점 결과

문제

문자열을 입력받고 Pn에 만족하는 게 몇 개나 포함되어 있는지 구하는 문제다.

 

처음엔 그냥 단순하게 생각했다.

 

서브태스크있는거 보고 만점은 못 받겠다 하며 풀었다.

 

50점 코드

n = int(input())

m = int(input())
s = input()

Pn = 'I'+'OI'*n
count = 0
for i in range(len(s)-len(Pn)+1) :
    sliceStr = s[i:i+len(Pn)]
    if sliceStr == Pn :
        count += 1

print(count)

Pn문자열을 우선 만들고 반복문을 돌리면서 만족하는 부분을 찾는 단순한 알고리즘이다.

 

50점 나오고 더 좋은 방법이 떠오르지 않아 인터넷을 찾아보니

 

파이썬에서 s[a:b]로 슬라이싱 했을 때, 시간 복잡도가 O(b-a)라는 글을 봤다.

 

즉 이 글에서 최악의 경우에 1,000,000 - 3에다가 for문을 n만큼 돌리니 시간복잡도는 거의 O(n^2)이었던 것.

 

그래서 코드를 수정했다.

100점 코드

n = int(input())

m = int(input())
s = input()

i = 0
count = 0
ans = 0
while i < m :
    if s[i:i+3] == 'IOI' :
        count += 1
        i += 2
        if count == n :
            ans += 1
            count -= 1
    else :
        count = 0
        i += 1


print(ans)

2
13
OOIOIOIOIIOII

다음과 같은 예제 입력이 있을 때

 

알고리즘은

 

index에서 +3 값을 슬라이싱 하고 IOI와 비교한다.

 

IOI가 맞을 경우

 

IOI의 길이를 카운팅 하기 위해 count변수에 1씩 더해준다.

 

그리고 i변수를 +2 해준다.

 

그럼 만약 문자열이

 

IOIOI이고 i=0일 때

 

s[i:i+3] => IOI

 

i+=2

 

다시 I부터 +3만큼 슬라이싱,

 

IOI면 count += 1

 

이 과정을 반복한다.

 

그러다 Pn의 n과 count이 맞을 때가 우리가 찾는 Pn의 문자열이므로 ans변수를 1씩 더해준다.

 

---

드디어 백준 티어 골드가 됐다 ㅎㅎ