[백준 9935] 문자열 폭발(Python)

1. 요약

폭발 문자열과 문자열이 주어질때 문자열 안에 폭발 문자열있으면, 폭발 문자열에 해당하는 문자는 없어지고, 뒤에있는 남은 문자열과 합쳐지게된다. 폭발은 연쇄적으로 발생할 수 있다. 우리가 해야할일은 폭발하고 남은 문자열을 출력해야한다. 만약 남아있는 문자열이 없으면 FRULA를 출력한다.(입력으로 주어진 폭발 문자열에서 같은 문자가 2번이상 나타나지 않는다.)

2. 아이디어

남은 문자열을 담는 스택을 이용한다. 스택의 크기가 폭발 문자열의 길이보다 같거나 크면, 스택 안에 폭발 문자열이 존재하는지 검사한다.
검사를 할 때, 스택에 있는 마지막 문자를 시작점으로 하여 폭발 문자열의 길이만큼 문자들을 가져오고 문자들을 합치고 비교한다. 앞서 언급된 내용을 문자열의 길이가 폭발 문자열보다 짧을 때까지 또는 폭발 문자열이 없을 때 까지 반복한다.

3. 코드

import sys

string = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()
bomb_size = len(bomb)
ans = []

for ch in string:
    ans.append(ch)
    while len(ans) >= bomb_size:
        tmp = []
        for i in range(-1, -bomb_size-1, -1): tmp.append(ans[i])
        tmp.reverse()
        tmp = ''.join(tmp)
        if tmp == bomb:            
            for _ in range(bomb_size):
                ans.pop()

        else: break

ans = ''.join(ans)
if ans: print(ans)
else: print('FRULA')