백준 9935 문자열 폭발(python)

x=input()

target=input()

while target in x:

    x=x.replace(target,'')

if len(x)==0:

    print('FRULA')

else:

    print(x)

 

처음에는 아무생각 없이 풀었는데 41퍼에서 시간초과 났다.

왜냐하면 while 문 안ㅇㅔ replace가 들어있어서.

replace는 문자열을 다 보고 target이 있는지 확인하는 함수니까 꽤 오래 걸림.

 

찾아봤는데 stack으로 풀라길래

x=input()

target=input()

stack=[]

for s in x:

    stack.append(s)

    if len(stack)>=len(target) and ''.join(stack[-len(target):])==target:

        for _ in range(len(target)):

            stack.pop()

result=''.join(stack)

if not result:

    print('FRULA')

else:

    print(result)

 

요렇게 풀어줬답니다.

예를 들어 target이 2자리일때

1. 문자열 하나씩 읽어서 stack에 추가

2. 마지막 2개가 target이랑 같으면 pop

 

 

 

코테 공부 어떻게 하는지 몰라서 프로그래머스랑 백준 왔다갔다 적당히 풀었는데 오늘 실버가 됐다. 백준 티어가 생각보다 아무것도 아니라서 당황스럽군.