[Algorithm🧬] 백준 9935 : 문자열 폭발

문제

import sys
import re
from collections import deque

readl = sys.stdin.readline

str = readl().rstrip()
pat = readl().rstrip()

stack = []


while str != re.sub(pat, '', str):
    str = re.sub(pat, '', str)



print(str if len(str) > 0 else "FRULA")

그냥 당연히 정규식이라고 생각해서 풀었는데, 다른 방식으로 풀 수 없나 생각해서 얼마 전에 공부한 자료구조 문자열 매치 알고리즘으로 풀었더니 시간 초과 남... -> 이 알고리즘을 스택으로 풀면 가능하다.

import sys
import re
from collections import deque

readl = sys.stdin.readline

str = readl().rstrip()
pat = readl().rstrip()

start = 0
j = 0


while pat in str:
    str = list(str)
    for i, s in enumerate(str):
        if s == pat[-1]:
            cnt = 0
            for j in range(len(pat)):
                if str[i - len(pat) + 1 + j] == pat[j]:
                    cnt += 1

            if cnt == len(pat):
                str = str[:i - len(pat) + 1] + str[i + 1:]
                str = ''.join(str)
                break


print(str if len(str) else "FRULA")

스택 이용

스택도 간소화하려는 노력이 좀 많이 필요함...

import sys

readl = sys.stdin.readline

str = readl().rstrip()
pat = readl().rstrip()


stack = []
for i, s in enumerate(list(str)):
    stack.append(s)
    if ''.join(stack[-len(pat):]) == pat:
        for _ in range(len(pat)):
            stack.pop()



print(''.join(stack) if len(stack) else "FRULA")