[골드 4] 백준 9935 - 문자열 폭발 (파이썬)

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

풀이

핵심 아이디어는 스택을 활용해 문자열을 한 글자씩 처리하면서 폭발 문자열(T)이 나타날 때마다 제거하는 것이다.

• 문자열 S에서 폭발 문자열 T가 등장하면, 그 부분을 제거한다.
• 제거 후 남은 문자열에서 다시 폭발 문자열이 등장할 수 있다면 또 제거한다.
• 이 과정을 반복해 최종 문자열을 구한다.
• 결과가 빈 문자열이면 "FRULA"를 출력한다.

stack = []
for i in range(len(S)):
    stack.append(S[i])  # 현재 문자를 스택에 추가

한 글자씩 stack에 넣으면서 문자열을 구성해 나간다.

if len(stack) >= len(T):
    same = True
    for j in range(len(T)):
        if stack[-len(T) + j] != T[j]:
            same = False
            break

현재 스택의 마지막 부분이 폭발 문자열 T와 같은지 확인하고,

stack[-len(T):]와 T를 비교하는 방식인데, 인덱스를 활용한 수동 비교로 구현한다.

if same:
    for _ in range(len(T)):
        stack.pop()

폭발 문자열이 발견되었으면 stack에서 제거한다.

코드

# 백준 9935 - 문자열 폭발
# 분류 : 스택

S = input()
T = input()

stack = []
for i in range(len(S)) :
    stack.append(S[i])

    if len(stack) >= len(T) :
        same = True
        for j in range(len(T)) :
            if stack[-len(T) + j] != T[j] :
                same = False
                break
        
        if same :
            for _ in range(len(T)) :
                stack.pop(-1)

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