<스택> 9935번 문자열 폭발 with 파이썬

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

 

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

 

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

 

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

 

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

정답비율

22.112%

알고리즘 분류

 #자료구조 #문자열 #스택

 

 

import sys
input = sys.stdin.readline

string = input().strip()
e = input().strip()
last_e = e[-1]
length = len(e)
stack = []
for s in string:
    stack.append(s)
    if last_e == s and ''.join(stack[-length :]) == e:
        del stack[-length:]

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

 

 - 스택에 문자열의 첫부분부터 담아가며, 폭발문자열과 일치할경우 그만큼을 빼주는 방식을 사용했다.

 

 - 그러나 접근방식은 맞는 것 같은데 계속 시간 초과가 났다. 

 

 - 시간을 줄이기 위해서 끝문자를 먼저 비교한 후, 일치할 경우에만 전체를 비교하는 방식을 택하였다.

 

 - 그래도 시간초과가 났는데, 재할당문을 사용했기 때문이었다. 이전에는 del이 아니라 stack = stack[:-length] 를 사용했었는데, 시간초과가 난 것이다. 재할당의 경우 문자열의 크기에 가까운 복잡도를 갖게 될 수도 있지만 끝 부분을 del하는, 즉 pop을 폭발문자열의 크기만큼 하는 것과 같은 방식은 폭발 문자열의 크기에 가까운 복잡도를 갖게되는 것으로 보인다. 참고로 pop보다 del의 연산이 더 빠르다. (반환이 없기 때문)

 

---

 

 

참고

 

9935번: 문자열 폭발

 

---