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

🌱 문제

9935번: 문자열 폭발

 

🌱 풀이

1. 입력 받기

str = deque(list((input().strip())))
bomb = list(input().strip())

전체 문자열과 폭발 문자열을 입력으로 받습니다. 빠른 pop연산을 위해서 전체 문자열은 queue로 바꿔줍니다.

 

2. 변수 초기화

stack = []

stack은 결과값을 저장할 변수입니다.

 

3. 스택과 큐 사용

while str:
    ch = str.popleft()
    stack.append(ch)
    if ch == bomb[-1] and stack[-len(bomb):] == bomb:
        for i in range(len(bomb)):
            stack.pop()

• 전체 문자열의 앞에서부터 하나씩 pop해서 stack에 넣습니다.
• pop한 문자가 폭발 문자열의 끝 문자와 같다면, 현재 스택에 들어가 있는 문자열의 끝에 폭발 문자열이 있는지 검사합니다. 폭발 문자열이 있다면 폭발 문자열의 길이만큼 stack에서 문자를 pop합니다.
  이때, 리스트 슬라이싱(stack = stack[:-len(bomb)])을 이용하면 시간초과가 납니다. 리스트 슬라이싱보다 pop 연산이 시간 복잡도가 훨씬 낮습니다.
• 폭발 문자열과 끝 문자를 비교하는 이유는, 폭발 후, 폭발 문자열과 같은 부분이 새롭게 생길 수 있기 때문입니다.

 

4. 출력

if not stack:
    print("FRULA")
else:
    print(''.join(stack))

• 만약, stack에 남아있는 문자가 없다면, 모든 문자열이 폭발한 것이므로 "FRULA"를 출력합니다.
• 그렇지 않다면 stack에 있는 문자열을 join하여 출력합니다.

 

🌱 정답 코드

# !/usr/bin/env python
# -*- coding: utf-8 -*-
# boj 9935 문자열 폭발

import sys
from collections import defaultdict
from collections import deque

input = sys.stdin.readline

str = deque(list((input().strip())))
stack = []
bomb = list(input().strip())
check = True

while str:
    ch = str.popleft()
    stack.append(ch)
    if ch == bomb[-1] and stack[-len(bomb):] == bomb:
        for i in range(len(bomb)):
            stack.pop()

if not stack:
    print("FRULA")
else:
    print(''.join(stack))