(Python/파이썬) - 백준(BOJ) 9935번 : 문자열 폭발

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

9935번: 문자열 폭발

---

• 문제 : 

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

 

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

 

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

 

 

 

---

• 풀이 :

스택을 사용하여 해결할 수 있는 문제였습니다.

 

처음엔 정규표현식으로 findall이 빈 list를 반환할 때 까지 폭발 문자열을 공백으로 replace하여 제거하는 방법을 사용했으나 시간초과에 걸렸습니다.

 

풀이는 다음과 같습니다

 

1 .폭발 문자열의 마지막 글자를 만났을 때 현재까지 탐색한 글자들을 위에서부터 탐색하여 폭발 문자열이 만들어지는지 확인

 

2. 만약 만들어진다면 폭발문자열만큼 pop() 연산 실행

 

 

---

• 소스코드 : 

정규표현식 사용 (시간초과)

import sys, re
input = sys.stdin.readline

S = input().strip()
del_S = input().strip()
while re.findall(del_S,S):
    S = S.replace(del_S,"")
print(S) if S else print("FRULA")

 

스택 사용 (문제 해결)

import sys
input = sys.stdin.readline

S = input().strip()
del_S = list(input().strip())
l = len(del_S)
last_word = del_S[-1]
answer = []
for i in S:
    answer.append(i)
    if i == last_word and answer[-l:] == del_S: # 폭발문자열을 찾은 경우
        for _ in range(l):
            answer.pop()
print(''.join(answer)) if answer else print("FRULA")