[백준 3111번] 검열 (Python3)

from collections import *

def delete(T,stack,A,p):
  while T:
    if p:
      stack.append(T.pop())
    else:
      stack.append(T.popleft())
    if stack[-1]==A[-1]:
      if stack[-N:]==A:
        for _ in range(N):
          stack.pop()
        return 1
  return
  
A = [*input()]; A2 = [*reversed(A)]; N = len(A)
T = deque([*input()])

front = []; back = []
while delete(T,front,A,0) and delete(T,back,A2,1):
  continue
while delete(back,front,A,1):
  continue
print(*front,sep="")

간단한 문자열 + 스택 응용문제

문자열 폭발 [백준 9935번] 문자열 폭발 (Python3) (tistory.com) 문제의 업그레이드 버전이라고 보면 된다.

 

문자열 폭발(stack에 문자열을 쌓다가 폭발문자열이 나오면 체크 후 pop) 알고리즘을 알고 있다는 전제 하에 풀이를 설명하면,

 

1. 두개의 스택 (front, back)을 만든다. 각각의 스택에는 문자열이 하나는 앞에서부터, 하나는 뒤에서부터 삽입된다.

2. 앞에서부터 문자열 폭발이 성공하면, 뒤에서부터 문자열 폭발을 한다. 폭발이 일어나지 않을 때까지 반복한다.

3. 폭발이 더 이상 일어나지 않으면 폭발문자열은 front와 back에 걸쳐있거나, 없거나이다. front에 back의 문자열을 삽입하면서 문자열 폭발을 한다.

4. 더 이상 문자열 폭발이 일어나지 않으면 front를 출력한다.

 

3번에서 폭발문자열이 더 존재할 경우 front와 back에 걸쳐있을 수밖에 없다는 것이 문제의 핵심 포인트이다. 이것을 인지하면 쉽게 해결할 수 있다.

 

 

오늘의 교훈) stack은 유용하다