[Python] 백준 5525 IOIOI_문자열

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

서브태스크가 있는 문제이다. 입력의 크기에 따라 소요되는 시간이 증가하지 않도록 시간 복잡도를 고려해서 구현해야한다.

---

50점

: 입력받은 n의 갯수만큼 IOI 문자열을 만든 뒤, 문자열 S의 인덱스에 하나하나 접근하며 P_n을 포함하는지 확인했더니 50점

 

👇 50점 소스

import sys
n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
s = sys.stdin.readline().rstrip()

p = ['OI'] * n
p_str = 'I' + ''.join(p)
count = 0

for i in range(m - len(p_str) + 1):
    if s[i] == 'I' and s[i:i + len(p_str)] == p_str:
        count += 1
print(count)

---

100점

• 문자열 S의 cur의 위치부터 3개의 문자가 'IOI' 인지 확인한다.
• 문자열 S에서 'OI'가 연속으로 n 번 나타나면 P_n의 갯수를 증가시키도록 했고, n번이 나타나기 전에 'OI'의 연속성이 깨지면 P_1의 갯수를 갖는 변수 count를 초기화 했다.
• P_n은 2의 간격으로 'IOI'가 n번 반복된다. 따라서 인덱스 cur은 2씩 증가시키면서 'IOI' 여부를 확인하면 된다.
• n = 2일 때 'IOIOIOI'에서 P_n은 몇개?
  👀 P_2 = 'IOIOI'
cur = 0 에서 IOI 체크 → IOIOIOI count = 1
cur = 2 에서 IOI 체크 → IOIOIOI count = 2 👉 P_2 포함 (count == n)
cur = 4 에서 IOI 체크 → IOIOIOI count = 2 👉 P_2을 또 포함하므로 (count == n)
  답 👉 'IOIOIOI'에서 P_n은 2개 존재한다.
  
  

👇 100점 소스

import sys
n = int(sys.stdin.readline().rstrip())
m = int(sys.stdin.readline().rstrip())
s = sys.stdin.readline().rstrip()

cur = 0
count = 0
result = 0

while cur < (m - 1):
    if s[cur:cur + 3] == 'IOI': # P_1 으로 체크
        count += 1
        cur += 2
        if count == n:      # P_1이 n개가 되면 
            result += 1     # P_n 갯수 증가
            count -= 1
    else:
        # cur부터 3개의 문자가 IOI 가 아니면 P_1 갯수 초기화
        count = 0
        cur += 1

print(result)