9935. 문자열 폭발

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

이해

• 문자열을 완전 탐색을 통해 더했다가 뺐다가 할 수 있지만, 최대 길이가 1,000,000 이므로 뺄때, 붙일 때 길이만큼 탐색하고, 제거/더해줌 반복되므로 시간 초과가 날 수 있음
• Stack 구조의 append/pop 연산을 통해 중복되는 반복을 제거하고, 최대 폭발 문자열의 길이만큼만 반복하게 하여 시간을 줄일 수 있음

구현

1. Stack으로 이용할 리스트 생성
2. Stack에 문자열 하나씩 저장하며, 길이가 폭발 문자열 길이 보다 길어졌을 때부터 폭발 문자열이 stack 내부에 있는지 확인 → 마지막 길이만큼만 확인하면 모두를 확인할 수 있음
   1. 만약 폭발 문자열이 있다면 pop 연산을 통해 제거
   2. 없다면 계속해서 append 연산을 통해 Stack 내부에 문자열을 추가

코드

# 9935 문자열 폭발
import sys
input = sys.stdin.readline


def solution(S:str, boom:str) -> str:
    # stack 구조 활용
    stack = []
    # 여러번 호출하는 boom 길이 미리 저장
    len_b = len(boom)
    # 반복 -> stack저장 -> 마지막 len_b까지 문자열이 폭탄이면 pop -> stack 저장
    for i in range(len(S)):
        stack.append(S[i])
        if len(stack) >= len_b and stack[-len_b:] == list(boom):
            for _ in range(len_b):
                stack.pop()
    # 있으면 문자열 없으면 FRULA 출력
    return "".join(stack) if stack else "FRULA"


if __name__ == "__main__":
    print(solution(input().strip(), input().strip()))