BOJ 5525 IOIOI Python

문제

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

접근1

첫 번째 입력받은 정수 n 만큼 I+IO*n의 문자열의 패턴이 3번째 입력받은 문자열에 몇 번 포함되는지 구하는 문제다.

1. 패턴 생성 후 해당 패턴의 길이를 저장
2. 구간별로 확인하기 위해 q라는 리스트 생성
3. 3번째 입력받은 문자열을 반복문에 하나씩 넣어가며 아래의 조건을 실행
   3.1 q에 저장된 마지막 리스트와 i 번째 문자가 다르면 q에 i의 문자를 추가해나간다 이때
   1에서 생성된 패턴의 길이보다 길어질 경우 q의 맨 앞에 요소를 삭제해 준다
   3.2 반대의 경우 리스트를 i 번째 문자로 초기화 시켜준다
   3.3 위의 조건을 반복하며 q의 길이가 1에서 생성된 패턴의 길이와 같고 q의 마지막 문자가 'I'일 경우 ans에 +1씩 누적시켜준다
   

코드1

import sys
input = sys.stdin.readline
n = int(input())
str1 = 'I'+'OI'*n
input()
a = len(str1)
str2 = input().strip()
q = [str1[0]]
ans = 0
for x in str2:
   if q[-1] != x:
       q.append(x)            
       if len(q) > a:
           q.pop(0)
   else:
       q = [x]
   if len(q) == a and q[-1] == 'I':
       ans +=1
print(ans)

2번째 서브 태스크에서 시간 초과가 났다
1중 반복문으로 깔끔하게 짰다고 생각했는데 아닌 거 같다

접근2

문자열의 길이가 길어지면 q의 길이도 늘어나 맨 앞의 요소를 pop을 하는 과정에서 시간이 오래 걸리는 거로 판단되어 q를 deque로 바꿔주고 실행하였는데 틀렸다고 나왔었다
단순 길이를 비교해서 n=1이고 OIOI가 들어왔을 때 4번째 I에서 POP이 진행되어 len(q) ==3이 되어 틀린 결과가 나왔던 것 같다
큐나 리스트에 넣어서 비교하는 대신 시작을 I로 하는 길이 비교를 하여 시간도 줄이고 IOI... 패턴을 비교하는 로직을 수정했다

코드2

import sys
from collections import deque

input = sys.stdin.readline
n = int(input())
#str1 = 'I'+'OI'*n
a = 2*n+1
input()
str2 = input().strip()
cnt = 0
isI = True
ans = 0
for xc,x in enumerate(str2):
    if isI and x =='I':
        isI = False
        cnt +=1   
    elif not isI and x =='O':
        isI = True
        cnt +=1
    else:
        if x =='I':
            cnt = 1
            isI=False
        else:
            cnt = 0
            isI = True
    if a == cnt:
        ans +=1
        cnt -=2
  
print(ans)

첫 번째가 위의 코드 2로 제출한 것이고
두 번째가 코드 1으 q를 deque로 수정, 패턴 비교 수정하여 제출한 것이다