알고리즘 스터디 - 백준 9935번 : 문자열 폭발

문제 해석

목적 : 상근이가 문자열에 폭발 문자열을 숨겨 놓았는데 이를 제외한 남은 문자열을 출력하는 것

• 시간 제한이 있고 추가 시간이 없으므로 시간복잡도 최적화를 하는 것이 좋을 것 같다.
• Python 에서 시간 복잡도를 줄이기 위해서는 문자열 -> List -> Set or Dict을 사용하면 좋다.
• 그러나, 폭발 문자열을 제거할 때 순서가 유지가 되어야 하는 것이 중요하다.

문제 해석을 잘못해 틀린 경우

문자열에서 C와 4를 각각 제거하는 줄 알았는데 그게 아니고 C4가 뭉쳐져 있는 것을 지워야 하는 것이다.

import sys

input = sys.stdin.readline

word = input().strip()
boom = set(input().strip())

entire = ''.join(i for i in word if i not in boom)

if entire == '':
    print("FRULA")
else:
    print(entire)

알고리즘 코드

문자열을 더하면서 마지막 글자와 비교해 같은 경우 지우는 방식으로 문제를 풀었다.

import sys
input = sys.stdin.readline

word = input().strip()
boom = list(input().strip())
answer = []

for i in word:
    answer.append(i)
    if len(answer) >= len(boom) and answer[-len(boom):] == boom:
        del answer[-len(boom):]

print(*answer if answer else "FRULA",sep="")