[백준/파이썬]9935 문자열 폭발

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

9935번: 문자열 폭발

문제

백준 9935 문자열 폭발

스택만 알면 쉽게 풀 수 있는 문제인 것 같다!

 

정답 비율이 낮은 이유는 아마 스택을 사용하지 않고 문자열이 폭발할 때마다 문자열 전체를 다시 반복 돌리는 코드를 제출한 사람이 많아서 그런 것 같다.

 

나도 처음에 문자열이 폭발할때 마다 다시 문자열 전체를 반복 돌려서 비교할까 했지만 입력 조건을 보면 문자열의 최대 길이는 100만이다.

 

100만을 몇번이나 반복을 해야 할 테니 이 방법으로 접근하면 시간초과가 나올게 뻔하다.

 

 

풀이는

 

문자열 S를 stack에 한글자씩 넣는다.

 

입력 예제 1을 예시로

 

mirkovC4nizCC44에서 m부터 차례대로 stack에 넣고, 폭발 문자열(C4)의 길이와 같거나 클 경우

 

스택의 끝에서부터 폭발 문자열의 길이만큼 slice 해서 폭발 문자열과 비교한다.

(stack = mirkovC4까지 들어왔을 때 끝에서 부터 폭발 문자열의 길이까지 slice 하면 C4가 slice 된다.)

 

만약 폭발 문자열과 같다면 폭발 문자열 길이만큼 stack을 pop 해준다.

 

이 과정을 반복하면 된다.

 

정답

s = input()
boom = input()

stack = []

for i in range(len(s)) :
    stack.append(s[i])
    if len(stack) >= len(boom) :
        if ''.join(stack[len(stack)-len(boom):]) == boom :
            for j in range(len(boom)) :
                stack.pop()
        

if len(stack) == 0 :
    print('FRULA')
else :
    print(''.join(stack))