[baekjoon] 백준 5525번(파이썬): IOIOI

문제

5525번: IOIOI

알고리즘

- IOI 단위로 최대 m번씩 탐색하여 문제를 수행한다.

- 현재 문자열이 IOI 이고 IOI 문자열 개수가 n 개라면 S안에 Pn이 포함된 것으로 카운트해준다.

- 현재 문자열이 IOI 이기 때문에 다다음 문자부터 확인해도 되므로 I를 + 2 해준다.

- 현재 문자열이 IOI 가 아니라면 다음 문자를 확인하고 IOI 문자열 개수를 0으로 초기화해준다.

코드

import sys

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

cnt = 0
i = 0
flag =0
# 시간 복잡도 : O(M) => I0I 단위로 최대 m번씩 탐색
while i < m - 1:
    # 현재 문자열이 IOI 일 경우
    if s[i - 1] == "I" and s[i] == "O" and s[i + 1] == "I":
        flag += 1
        
        # IOI 문자열 개수가 n 개라면  
        if flag == n: 
            flag -= 1 # 문자열 개수 -1
            cnt += 1 # 카운트
            
        i += 2 # 현재 문자열이 IOI 이기 때문에 다다음 문자부터 확인하기 위해 i + 2를 해준다.  
        continue
    
    i += 1 # 현재 문자열이 IOI 가 아니라면 다음 문자부터 확인 
    flag = 0 # IOI 문자열 개수는 0으로 초기화
    
print(cnt)

 

50점

import sys

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

p = "IOI"
for _ in range(1, n):
    p += "OI"

cnt = 0

# 시간 복잡도 : O(NM) => n개를 m번씩 탐색
for i in range(m):
    if s[i:len(p) + i] == p:
        cnt += 1

print(cnt)

시간 초과로 인해 50점을 받게 되었다. 

마지막 반복문 과정에서 Pn을 m번씩 탐색하는 것을 확인할 수 있다. 이때, 시간 초과가 나오는 것을 알 수 있고 시간을 줄이기 위해 최대 m번만에 문제를 수행할 수 있게 코드를 작성했다.

O(NM) => O(M)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법