문자열이 최대 100만길이만큼 길 수 있기때문에 문자열 자체를 변경하는건 시간초과가 날 것이라 생각했다.
그래서 처음에 생각한 방법은 문자열 길이만큼의 체크리스트를 만들어 폭발 문자열에 해당하는 부분을 체크하고, 체크하지 않은 부분만 출력하는 방법이었다.
해당 코드는 다음과 같다.
import sys
input = sys.stdin.readline
from collections import deque
sys.setrecursionlimit(10**6)
seq1 = input().strip()
seq2 = input().strip()
L1 = len(seq1)
L2 = len(seq2)
check = [0]*L1
def explode(start,now,cnt):
if now+1 < L1:
if seq1[now+1] == seq2[0] and check[now+1] == 0:
explode(now+1,now+1,0)
if now+L2 < L1:
if check[now] == 1:
explode(start,now+L2,cnt)
return
if seq1[now] == seq2[cnt]:
if cnt == L2-1:
for i in range(start,now+1):
check[i] = 1
return
if now+1 < L1:
explode(start,now+1,cnt+1)
x = -1
while True:
x = seq1.find(seq2[0],x+1)
if x == -1:
break
if check[x] == 1:
continue
explode(x,x,0)
if sum(check) == L1:
print("FRULA")
else:
for i in range(L1):
if check[i] == 0:
print(seq1[i],end="")
print()
하지만 처음에는 recursion error가 발생하였고, 재귀제한을 풀어주자 시간초과가 발생하였다.
재귀함수로 푸는건 불가능하다는 것을 깨닫고 어떤 방식으로 풀어야할까 고민하다가 질문게시판에서 이 문제를 stack으로 풀어야 한다는 것을 알게되었다.
다음은 stack을 이용한 코드이다.
import sys
input = sys.stdin.readline
from collections import deque
seq1 = input().strip()
seq2 = input().strip()
stack = deque()
def check():
count = 0
for i in range(len(seq2)):
try:
if stack[-1-i] == seq2[-1-i]:
count += 1
except:
return False
if count == len(seq2):
return True
for i in range(len(seq1)):
stack.append(seq1[i])
if seq1[i] == seq2[-1]:
if check():
for i in range(len(seq2)):
stack.pop()
if stack:
print("".join(stack))
else:
print("FRULA")
문자열을 스택에 계속 쌓다가, 폭발문자열의 마지막 문자와 같은 문자가 나오면 check 함수를 실행하여 같은 문자열인지를 확인하고, check 함수가 True를 출력하면 폭발 문자열 길이만큼을 pop하는 코드이다.
확실히 stack을 이용하니 훨씬 더 깔끔하고 쉽게 문제를 해결할 수 있었다.
오늘의 교훈) stack 자료 구조를 문제풀이에 이용하자