[Python] 백준 5525번 - IOIOI

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

5525번: IOIOI

 

혼자 힘으로 풀었는가? △ (부분점수 50점)

알고리즘 분류
 - 문자열

문제

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	50	N ≤ 100, M ≤ 10 000.
2	50	추가적인 제약 조건이 없다.

---

문제를 보자마자 제일 먼저

 

슬라이싱 하면 끝이네

 

라고 생각했다.

 

import sys
input = sys.stdin.readline

n = int(input())
s = int(input())
st = input()

point = "OI"*n
point = "I"+point
cnt = 0
for i in range(s - len(point)):
    if st[i] == "I":
        if st[i:i+len(point)] == point:
            cnt+=1
print(cnt)

point 변수에 표본이 될 IOI를 만들어 주고

 

반복문을 통해서 조건을 만족하는 IOI를 찾아서 카운트를 증가시켜준다.

 

단순했다.

그리고 틀렸다.

 

---

이후 나는 해법을 도저히 찾을 수가 없었다.

 

그래서 구글에 slice의 시간 복잡도를 검색했다.

 

https://wayhome25.github.io/python/2017/06/14/time-complexity/

파이썬 자료형 별 주요 연산자의 시간 복잡도 (Big-O) · 초보몽키의 개발공부로그

 

위의 사이트를 참고해서 보았다.

 

Slice

l[a:b]

O(b-a)

l[:] : O(len(l)-0) = O(N)

slice의 경우 l[a:b] -> O(b-a) = O(N)

 

for 반복문도 O(N)

 

총합 \(O(N^2)\)의 시간 복잡도를 가진다고 생각했다.

 

또한 그래도 모르겠어서 코드를 참고하기 위해

 

https://aia1235.tistory.com/30

[백준] 5525 IOIOI (python 파이썬)

위 블로그를 참고했다.

 

import sys
input = sys.stdin.readline

n = int(input())
m = int(input())
s = input()
i = cnt = ans = 0
while i < (m-1):
    if s[i:i+3] == "IOI":
        cnt+=1
        i+=2
        if cnt == n:
            ans+=1
            cnt-=1
    else:
        cnt=0
        i += 1
print(ans)

while - O(N)

s[i : i+3] - O(N)

 

위와 동일한 시간 복잡도를 가질 거라 생각했다.

 

하지만 이 코드는 시간 초과가 뜨지 않은 정답이었다.

 

심지어 1 항목에 대해선 시간도 36ms -> 52ms로 더 느려졌으나

 

이 코드가 정답이었다.

 

s[a:b] -> O(b-a) = O(N) 

 

1. s[i : i+len(point)] = O( (i+len(point)) - i ) -> O(len(point)) = O(N)

2. s[i : i+3] = O(3) = O(N)

 

위와 같이 생각했는데 내가 모르는 무언가가 있는 것 같다...

 

나중에 시간 복잡도에 대해서 좀 더 공부하고 다시 봐야 할 것 같다.

 

위의 차이가 어떤 극명한 차이를 만들어내었는지 잘 모르겠다.

 

아시는 분 혹시라도 이 게시글을 보게 된다면 댓글로 내용을 공유해주신다면 정말 감사합니다.