[알고리즘] 백준 9935 문자열 폭발

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

자주 볼 수 있는 문자열 관련 스택 문제였지만, 한번도 시도해본적 없느 풀이법을 발견해서 포스팅하게 되었다.

이전에는 한 문자에 대해서 어떤 조건에 해당한다면 pop을 시키는 식이었다면, 이번 문제는 입력된 문자열에서 폭탄으로 지정된 문자열 부분을 pop 시킨뒤 남은 문자열만 출력하면 되는 문제였다.

한 문자열이 중복에 해당하는지 판단하기 위해서, 폭탄의 문자열에 포함된 문자가 등장할 경우 인덱스를 하나씩 증가시켜주고 폭탄 문자열 길이와 인덱스가 동일해질 경우 해당 문자열 길이 만큼 pop을 시켜주는식으로 구현을 하려고 했었다.

그러나 위와 같이 구현할 경우, C4가 폭탄 문자열이고 입력값으로 aaaCCC444와 같이 문자열이 들어온 경우를 잡아낼 수 없을 것 같았다.

그래서 결국 내가 참고한 풀이는 아래와 같다.

import sys

inputs = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()

stack = []

for i in range(len(inputs)):
    stack.append(inputs[i]) # 일단 스택에 문자 추가
    # 만약 스택의 top부터 폭탄 문자열 길이 만큼의 슬라이싱한 문자열이 bomb과 같은 값일 경우
    if ''.join(stack[-len(bomb):]) == bomb:
        for _ in range(len(bomb)): # bomb의 문자열 길이 만큼 pop을 시켜줌(= 폭탄 문자열만 pop)
            stack.pop()

if stack: # 스택에 남아있는 내용들만 합쳐서 결과 출력
    print(''.join(stack))
else: # 스택이 비어있다면 모두 폭탄이라는 뜻이므로 FRULA 출력
    print('FRULA')