[백준] 9935번: 문자열 폭발(Python)

문제 링크

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

9935번: 문자열 폭발

 

풀이

풀이 설명

• 분류: 문자열
• replace 를 썼더니 시간초과
  • replace 의 빅오: O(문자열의 길이 * (교체할 문자열의 길이 + 교체되는 문자열의 길이/교체할 문자열의 길이))
  • 그러므로 replace > slice > del 순서로 시간이 적게 걸린다는 것을 생각하자. 
  • 안될 경우 slice/del 로 바꿔보기
  • slice - O(L[a:b]) => O(b-a)
  • del - O(N)

sentence = input()
burst = input()

# stack
stack = []
length = len(burst)


for i in range(len(sentence)):
    stack.append(sentence[i])
    if ''.join(stack[-length:]) == burst:
        del stack[-length:]

answer = ''.join(stack)

if not answer:
    print('FRULA')
else:
    print(answer)