[BOJ 9935] 문자열 폭발(Python)

문제

문자열 폭발

---

문제 해설

스택을 이용해 문자열을 검사하는 문제입니다. 특히 문자열과 스택을 이용한 문제를 자주 볼 수 있기 때문에 연습하는 것이 좋다고 생각합니다.

1. 문자열을 받습니다.
2. 한 글자씩 스택에 넣고 넣을때마다 스택의 마지막 부분이 폭탄 문자열과 일치하는지 검사합니다.
3. 일치하면 그 부분을 제거합니다. (pop)

시간 복잡도는 문자열 전체(n)를 검사하는 도중 폭탄 문자열(x) 까지 검사하기 때문에 O(nx)로 제한 시간안에 들어올 수 있습니다.

---

풀이 코드

import sys

input = sys.stdin.readline
string = input().rstrip()
boom = list(map(str, input().rstrip()))
stack = []

for s in string:
    # 스택에 한글자씩 넣는다.
    stack.append(s)
    # 넣을때 마다 스택을 검사
    if len(stack) >= len(boom) and stack[len(stack) - len(boom) :] == boom:
        for _ in range(len(boom)):
            stack.pop()
print("".join(stack)) if stack else print("FRULA")

---