[백준] 9935번 : 문자열 폭발

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

해당 문제를 처음에는 파이썬 내장함수로 문제를 풀었지만, 시간복잡도가 o(n^2)으로 시간초과가 발생한다. 해당 문제를 해결하기 위해서 스택 자료구조 를 활용하여 O(n)으로 문제를 풀 수 있다.

 

개선 이전 ( 내장함수 in , replace 함수 사용 )

char = input()
bumpchar = input()
while bumpchar in char:
    char = char.replace(bumpchar, "")
    
if char == "":
    print("FRULA")
else:
    print(char)

이후 개선 코드 ( 스택 자료구조 사용 )

char = input()
bumpchar = input()
length = len(bumpchar)
stack = []
for i in range(len(char)):
    stack.append(char[i])
    if bumpchar == ''.join(stack[-length:]):
        for _ in range(length):
            stack.pop()

newstr = ''.join(stack)
if newstr == "":
    print("FRULA")
else:
    print(newstr)