[백준BOJ] 9935번 문자열 폭발.py

 

백준 저지에서 문자열 폭발을 파이썬을 통해 풀어 보았다. 

 

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

 

9935번 문자열 폭발.py

GitHub - tomy9729/Algorithm: 🐗 내가 직접 작성한 내 코드 🐗

 

 

1259번 팰린드롬수

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
- 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

설명

다른 사람들의 코드를 보니까 보통 KMP를 통해서 많이 풀었던데 예전에 비슷한 문제를 스택으로 풀었던 기억이 있어서 그렇게 풀어봤다. 

 

전체 문자열의 문자를 하나씩 스택에 넣는다. 넣을 때마다 스택의 끝부터 폭발 문자열인지 확인한다. 만약 폭발 문자열이라면 바로 삭제를 진행한다. 이 과정을 끝까지 반복하면 최종적으로 모든 폭발이 끝난 후 남은 문자열만 스택에 남게 된다.

 

아쉬운 점이 있다면 python3 컴파일로는 시간 초과가 발생하고 pypy3에서만 통과한다.

코드

#9935번 문자열 폭발.py
from collections import deque
str = input()
boom = input()

stack=deque()

for i in range(len(str)) : 
    stack.append(str[i])
    if len(stack) < len(boom) : 
        continue
    check = 0
    for j in range(len(stack)-len(boom),len(stack)):
        if(stack[j] != boom[j-len(stack)+len(boom)]):
            check=1
    if check==0:
        for j in range(len(stack)-len(boom),len(stack)):
            stack.pop()

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