[백준] 9935 문자열 폭발 Python

 

문자열을 순회하다가 폭발 문자열이 발견되면 폭발시키고 뒤에 남은 문자열을 이어붙여준다.

이어붙이면서 폭발 문자열이 또 발생될 경우, 다시 폭발시키고 이어붙여준다.

 

 

정말 여러 방법으로 접근했지만, 계속되는 시간초과 문제로 .....😢

구글링을 통해 스택으로 간단하게 풀 수 있다는 것을 알게 되었다. 😂

 

스택으로 접근한 풀이이다.

 

일단 문자열을 순회하면서 스택에 넣어준다.

그러다가 폭발 문자열의 끝값과 같은 문자가 발견되면

폭발 문자열 길이 만큼 스택 top부터 가져와서 비교한다.

만약 같은 문자열이면 폭발 문자열만큼 스택에서 pop을 시켜준다.

 

결국 스택에 남은 문자들을 합한 것이 남아있는 문자열이다.

 

정답코드

total = list(input())
pang = input()

stack = []

for i in range(len(total)):
    check = True
    stack.append(total[i])

    # 마지막 문자가 현재 문자와 일치하면
    # 스택에 있는 값들을 하나씩 뽑아내서 폭탄문자열과 같은지 확인한다.
    if stack[-1] ==pang[-1]:
        if len(stack) >= len(pang):
            for j in range(len(pang)):
                if pang[-1-j] != stack[-1-j]:
                    check = False
            if check:
                # 같은 값이면 그만큼 stack에서 빼준다.
                for j in range(len(pang)):
                    stack.pop()
       

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