파이썬 알고리즘 260번 | [백준 9935번] 문자열 폭발 (FRULA ! ) - 두번째인데 다시 풀려니 못 푼~ 문제~

260. 문자열 폭발

1) 어떤 전략(알고리즘)으로 해결?

2) 코딩 설명

• 스택

<내 풀이>

import sys

strr = str(sys.stdin.readline().strip())
explode = str(sys.stdin.readline().strip())
stack=[]

for s in strr : 
    stack.append(s)
    if stack[-1]==explode[-1] and len(stack)>=len(explode) :
        if "".join(stack[-len(explode):len(stack)])==explode :
            #stack = stack[0:len(stack)-len(explode)]
            # 이렇게 대치해주는 것이아니라 , stack 의 pop 기능 사용해야 됨
            for i in range(len(explode)) :
                stack.pop()
            
if len( "".join(stack)) ==0 :
    print("FRULA")

else : print("".join(stack))

< 내 틀렸던 풀이, 문제점>

시간초과1 - 2프로

import sys
strr = str(sys.stdin.readline().strip())
explode = str(sys.stdin.readline().strip())
while strr and len(strr)>0 and explode in strr:
    # print(strr)
    strr = strr.replace(explode,'',1)

if len(strr)==0 :
    print("FRULA")
else : print(strr)

시간초과2 - 47프로

import sys
strr = str(sys.stdin.readline().strip())
explode = str(sys.stdin.readline().strip())
while strr and len(strr)>0 and explode in strr:
    # print(strr)
    strr = strr.replace(explode,'')

if len(strr)==0 :
    print("FRULA")
else : print(strr)

스택을 사용하라

import sys

strr = str(sys.stdin.readline().strip())
explode = str(sys.stdin.readline().strip())
stack=[]

for s in strr : 
    stack.append(s)
    if stack[-1]==explode[-1] and len(stack)>=len(explode) :
        if "".join(stack[-len(explode):len(stack)])==explode :
            stack = stack[0:len(stack)-len(explode)]
            
if len( "".join(stack)) ==0 :
    print("FRULA")

else : print("".join(stack))

<반성 점>

<배운 점>

• stack 의 pop, push 가 시간복잡도가 O(1) 이다.

스택의 연산에는 다음과 같은 것들이 있다.

• push : 스택의 맨 위(뒤)에 데이터를 삽입하는 연산. 시간복잡도 O(1)
• pop : 스택의 맨 위(뒤)에서 데이터를 꺼내는 연산. 시간복잡도 O(1)