[백준] 9935번 문자열 폭발 (Python)

백준 9935 문자열 폭발

자주 보이는 유형이라서 정리하려고 한다. 이렇게 문자열에서 해당하는 문자열이 있는지 확인하고 삭제하는 문제는 스택을 활용하면 쉽게 해결할 수 있다.

1. 현재까지 bomb 문자열의 몇 번째 문자열까지 동일한지 저장할 i 변수를 설정한다.
2. 다음 bomb 문자열과 일치하는 문자열이 입력된다면, i를 1만큼 증가시키고 스택에 넣는다. 여기서 i의 의미는 "다음에 확인할 bomb 인덱스"이다.
3. bomb 문자열이 모두 들어온다면 해당 개수만큼 stack에서 꺼내주고 stack의 마지막 문자열에 저장된 i 값을 가져온다.
4. 예상한 bomb 문자열 외의 문자열이 들어온 경우 2가지로 나누어 해결한다.
   • bomb의 첫 번째 문자열과 같다면 i를 1로 바꾸어 스택에 넣어준다.
   • 그 외의 문자열이라면 i를 0로 설정하여 스택에 넣어준다.

import sys
from collections import deque

input = sys.stdin.readline
stack = deque()
inputString = input().strip()
bomb = input().strip()

i = 0
n = len(bomb)
for s in inputString:
    if s == bomb[i]:
        if i == n - 1:
            for _ in range(n - 1):
                stack.pop()
            if stack:
                i = stack[-1][1]
        else:
            i += 1
            stack.append([s, i])
    else:
        i = 0
        if s == bomb[0]:
            i = 1
        stack.append([s, i])

print("".join([x[0] for x in stack]) if stack else "FRULA")