백준(9935) - 문자열 폭발 Python

백준(9935) - 문자열 폭발

문제풀이: 문자열, 스택, 파이썬

풀이 방법을 떠올리고 파이썬에 익숙하다면 쉽게 구현할 수 있는 문제다.

입력받은 문자열을 하나씩 스택에 쌓아가면서 입력 받은 문자가 폭탄의 마지막 문자와 일치하는 경우,

그 앞을 확인해서 폭탄인지 확인하고 맞다면 스택에서 폭탄을 제거해나가며 시간복잡도 O(n) 으로 풀 수 있는 문제다.

ss = input()
bomb = input()
stack = []
bomb_len = len(bomb)
for s in ss:
    stack.append(s)
    if s == bomb[-1] and ''.join(stack[-bomb_len:]) == bomb:
        del stack[-bomb_len:]
res = ''.join(stack)

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