[백준] 문자열 폭발 : 9935 Python

이 문제는 자료구조 (스택)에 관한 문제였다. 

문제를 간략히 설명하자면, 입력으로 문자열과 문자열 폭탄이 주어진다. 문자열이 문자열 폭탄을 포함하고 있으면 폭탄 부분은 제거되고 앞뒤로 이어지는 새로운 문자열이 된다.

백준에 자료구조 문제들이 그렇듯 쉬운 방법(re라이브러리) 같은 것들로 풀면 당연히 시간 초과가 나는 문제이다.

결국 가장 효율적으로 폭탄들을 제거하면서 새로운 문자열을 만들어가야 한다. 반복을 자주 할수록 시간 소요가 많이 되기 때문에 최소한의 반복문으로 문자열을 만들 방법을 생각해야 한다.

나의 아이디어는 이렇다.
1. 문자열들을 순서대로 스택에 담는다.
2. 내가 담는 문자열이 문자열 폭탄의 끝 글자와 같으면 스택을 검사한다.
3. 이때, 문자열 폭탄이라면 스택에서 제거한다. 문자열의 첫 글자를 검사하는 것이 아닌 끝 글자를 제거하는 이유는 폭탄을 제거하기 전에는 폭탄이 아니었지만, 제거 후 폭탄이 된 문자도 있을 수 있기 때문이다.

이렇게 한다면 for문 한 번으로 모든 폭탄을 제거할 수 있다. 

이 과정을 코드로 나타내면 아래와 같이 된다.

문자열 폭발 코드

문제를 푼 과정에서 함수 remove를 사용하지 않고, 예약어 del을 사용한 이유는 del은 인덱스를 이용하여 리스트의 내용물을 제거할 수 있기 때문이다.

스택을 통해 문자열에서 원하지 않는 문자를 빼내는 알고리즘은 알아둘 필요가 있는 것 같다. 속도도 다른 방법들에 비해 훨씬 빠른 것이 느껴졌고 바로 다음 문제인 검열이라는 문제에서도 이 알고리즘을 활용하기 때문이다.