[백준 파이썬] 9935 문자열 폭발

📌문제 출처

백준 단계별 문제풀이 - 스택 2
https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

❓ 문제

 

❗ 풀이

• stack 활용

📗 풀이 코드

import sys
input = sys.stdin.readline
s, ex = input().rstrip(), input().rstrip()
stack = []
lx = len(ex)
for i in s :
    stack.append(i)
    if ''.join(stack[-lx:]) == ex : # stack의 마지막 len(ex)개가 폭탄 문자열이라면
        for _ in range(lx):
            stack.pop()
print(''.join(stack) if stack else 'FRULA')

📗 코드 해설

• 입력 문자열을 한글자씩 확인하며 stack에 넣어준다.
• stack의 마지막 lx만큼 뽑아서만든 문자열이 폭발문자열과 같다면 폭발문자열 길이만큼 stack에서 pop()해준다.
  이렇게 pop으로 뽑아줘야 시간이 단축된다.
• stack에 어떤 순서에 확인하던 항상 폭발문자열의 길이만큼 확인해주기에 모든 문자열을 한번씩만 확인하면 모든 폭발문자열의 가능성을 확인하게 된다.
• 마지막에 stack에 남아있는 문자열을 출력해준다.