[Python Algorithm] 백준 문자열 폭발 - 9935

---

풀이 과정

첫번째 시도

처음에는 그냥 보자마자 python에 내장되어있는 replace 함수를 사용하면 간단하게 해결이 가능하겠다는 생각이 들었다.
replace를 적용한 문자열과 이전 상태의 문자열의 상태를 비교하여 같을 때까지 반복을 돌려주고, 남은 문자열이 없다면 "FRULA"를 있다면 해당 문자열을 출력해주는 식으로 구현하였다.

s = input()
bomb = input()

origin = s
s = origin.replace(bomb, '')
while s != origin:
  origin = s
  s = origin.replace(bomb, '')

if s == '':
  print("FRULA")
else:
  print(s)
  

하지만 이렇게 구현하면 시간초과로 통과하지 못한다...

두번째 시도

모든 문자열을 계속해서 확인하는 방식이 아닌 다른 방법을 생각해내야 했다.
결국 받은 문자열을 스택에 넣고, 마지막 문자를 bomb과 비교하여 같다면 해당 문자를 stack에서 지워주는 방식으로 구현하기로 하였다.

이렇게 구현하니 통과할 수 있었다.

---

최종 코드

string = list(input())
bomb = input()
length = len(bomb)
stack = []

for char in string:
  stack.append(char)
  if ''.join(stack[-length:]) == bomb:
    del stack[-length:]

if (len(stack) == 0):
  print("FRULA")
else:
  print(''.join(stack))

---

결과

---

Link

문자열 폭발 문제 출처
GitHub 코드