백준(BOJ) 3111 검열(Python)

문제 내용

 

문자열 테크닉으로 해결할 수 있는 문제였다.

앞에서부터 stack(L1)에 문자를 하나씩 넣다가 L1의 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 A와 같으면 len(A)개 만큼 pop, 그 다음에는 새 stack(L2)에 뒤에서부터 문자를 하나씩 넣다가 L2의 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 reversed(A)와 같으면 len(A)개 만큼 pop한다.

위의 모든 작업이 끝나면 L2에서 pop한 문자를 L1에 push하면서 마지막 index부터 len(A)만큼 문자열을 체크해서 그 문자열이 A와 같으면 len(A)개 만큼 pop해준다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

A=input()
B=list(reversed(A))
A=list(A)
T=input()
nA=len(A)
nT=len(T)
start=0
end=nT-1
t=1
L1=[]
L2=[]
while start<=end:
    if t:
        L1.append(T[start])
        start+=1
        if L1[-nA:]==A:
            L1[-nA:]=[]
            t=0
    else:
        L2.append(T[end])
        end-=1
        if L2[-nA:]==B:
            L2[-nA:]=[]
            t=1
while L2:
    L1.append(L2.pop())
    if L1[-nA:]==A:
        L1[-nA:]=[]
print(''.join(L1))

 

엄청 헤맸다.

처음에는 복잡하게 하기 싫어서 파이썬의 장점 중 하나인 잘 구현된 메서드를 사용해보려 했으나, 시간 초과가 터졌다.

그래서 kmp를 변형해서도 해봤지만 출력 초과랑 시간 초과가 터져서 처음부터 단순하게 해서 풀었다.

확실히 플래티넘 문제는 좀 빡센 것 같다.