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

문자열이 최대 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 자료 구조를 문제풀이에 이용하자