[BOJ 9935] 문자열 폭발 (Python)

풀이

이 문제의 포인트는 스택과 문자열 인덱스 및 슬라이싱을 활용하는 것이다. 보통 문자열 일치 문제는 문자열의 끝에 집중하는 스택을 활용하여 푼다.
(특정 조건을 만족하는 문자열 길이 문제는 표를 만들어서 DP를 , 찾고자 하는 문자열의 접두사와 접미사가 일치한다면 KMP 알고리즘으로 푼다.)

1. 문자열의 각 문자를 하나씩 스택에 삽입한다.

2. 스택의 맨 위에 있는 문자(top)와 폭발 문자열의 맨 마지막 문자가 일치하고, 스택의 맨 위에 있는 문자에서부터 폭발 문자열의 길이만큼의 문자열이 폭발 문자열이라면 스택에서 폭발 문자열을 삭제한다.

3. 위 과정을 주어진 문자열 길이만큼 반복한다.

코드

import sys

input = sys.stdin.readline
string = input().rstrip()
bomb = input().rstrip()
stack = []

for i in range(len(string)):
    stack.append(string[i])
    # stack[-x:] -> 문자열의 오른쪽에서부터 x번째 ~ 마지막 까지 잘라낸다.
    # 문자열 인덱스 및 슬라이싱 활용을 잘하자!
    if stack[-1] == bomb[-1] and ''.join(stack[-len(bomb):]) == bomb:
        del stack[-len(bomb):]

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