[스택 심화]9935-문자열 폭발

폭8

단계별로 풀어보기 스택 2에 있는 문자열 폭발이다. 

문제 조건에서 알 수 있듯이, 폭발 문자열이 사라질 때까지 폭발 문자열을 삭제해주면 된다.

 

1. 아이디어

python replace를 쓰니까 광탈...

직접 replace를 구현해줄 방법이 있을까?

->스택사용!

파이썬은 문자열 합치기 기능(join)이 있으므로 구현하기 간단하다.

2. 코드

s = input()
boom = input()
stack = []
m = len(boom)
for i in s:
    stack.append(i)
    while stack and "".join(stack[-1*m:]) == boom:
        if "".join(stack[-1*m:]) == boom:
            for j in range(m):
                stack.pop()
if stack:
    print("".join(stack))
else:
    print("FRULA")

 

원리: stack에 문자를 하나씩 추가해가면서 폭발 문자열을 삭제해준다.

문자열의 길이가 1,000,000보다 작거나 같으므로 시간 복잡도는 이를 넘지 못한다.

O(n)