9935: 문자열 폭발

풀이 시간

• 20m
• 알고리즘 분류를 보고 stack을 활용해서 풀이함

구현 방식

• 입력받은 문자열을 순회하면서 문자 하나씩 stack에 append해줌
• stack에 넣어줄 때마다 stack의 tail - bomb_length부터 tail까지가 bomb와 같은지를 확인하고 같다면 바로 bomb_length만큼 pop해줌

코드

import sys

string = sys.stdin.readline()[:-1]
bomb = sys.stdin.readline()[:-1]

stack = []
bomb_length = len(bomb)

for i in range(len(string)):
    stack.append(string[i])
    if ''.join(stack[-bomb_length:]) == bomb:
        for _ in range(bomb_length):
            stack.pop()

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

결과

• 처음에는 그냥 while문을 돌면서 python의 replace를 사용하려했으나 역시나 시간초과가 발생했다
• 문자열을 한 문자씩 순회하며 stack을 통해 들어오는 문자가 폭탄 문자열을 만족한다면 바로 pop해주는 방식으로 구현하여 1중 for문으로 해결할 수 있었다.