[Python] BOJ 9935 문자열 폭발

요구사항 

• 시간 제한: 2초 
• 메모리 제한: 128MB
• 폭발 안할 거 처럼 보여도 (예제 입력1) 폭발하고 왼쪽 문자열과 오른쪽 문자열과 합쳤을 때, 폭발 문자열이라면 폭발한다.
• 남아 있는 문자가 없는 경우 FRULA를 출력한다. 

설계 1 

• 문자열에 폭발 문자열을 반복적으로 찾는다.
• 남아 있는 문자가 없는 경우 "FRULA"를 출력한다.

import sys
input = lambda: sys.stdin.readline().rstrip()

sentence = input() # 입력 받은 문자열
bomb = input()     # 폭발 문자열

while bomb in sentence:
    sentence = sentence.replace(bomb, "")

if not sentence:
    print("FRULA")
    exit()

print(sentence)

• 시간 초과 
• 이유는 아마도 replace할 bomb 을 찾기 위해 O(N)이 걸릴거고 만약 최악의 경우 O(N**2)이 걸림.
• 문자열의 길이는 1,000,000 폭발 문자열은 36 
• 문자열의 길이가 최대 1,000,000이기 때문에 최악의 경우 2초를 넘기는 것.. (되다 말더라..)

설계 2

• 문자열을 돌면서 하나씩 스택에 넣는다.
• 쌓인 스택과 bomb이 일치할 때, stack에서 bomb의 길이만큼 제거한다. 

import sys
input = lambda: sys.stdin.readline().rstrip()

sentence = input() # 입력 받은 문자열
bomb = input()     # 폭발 문자열
bomb_len = len(bomb)
stack = []

for char in sentence:
    stack.append(char)

    if ''.join(stack[-bomb_len:]) == bomb:
        del stack[-bomb_len:]

result = ''.join(stack)

if result:
    print(result)
else:
    print("FRULA")

• [-bomb_len] 했을 때 끝에서부터 해당 길이만큼 똑바로 출력한다.
• 예를 들어 bomb_len == 4 이고 stack = 'abcd' 라고 하자.
• stack[-bom_len] == 'abcd' 이다. dcba 라고 생각할 수 있다. 헷갈렸음.