1. 문제
  2. 접근
  3. 풀이

문제

BOJ 9935번 문자열 폭발

접근

문자열 문제를 아직 많이 다뤄보지 못해서 처음 접근할 때 어려움이 있었다.
주어진 문자열에서 폭발 문자열을 찾고 모두 지우면 되는데, 문자열을 지우고 난 후 연쇄적으로 생성되는 폭발 문자열도 지워야 하는 게 어려운 점이었다.
예를 들어, 문자열이 ACC44, 폭발 문자열이 C4인 경우 앞에서부터 폭발문자열의 검사를 시작하면 끝마쳤을 때 AC4가 남게된다. 이후 한번 더 검사를 해야 최종문자열 A만 남는다.
그래서 처음에는 앞에서부터 폭발 문자열을 찾는 알고리즘을 함수로 만들고, 폭발 문자열을 검색할 수 없을 때 까지 재귀적으로 실행하려 했다.
몇 번 실패하고 다른 사람들의 풀이를 참고해보니, 문자열을 뒤에서부터 검색하면 굳이 재귀를 하지 않아도 되는 방법이 있었다.

  1. 입력 문자열의 앞에서부터 한 문자씩 stack에 추가한다.
  2. 추가한 문자가 폭발 문자열의 마지막 문자와 일치하면, 문자의 앞쪽으로 폭발 문자열과 일치하는지 검사한다. 일치한다면 stack에서 폭발 문자열을 제거한다.
  3. 입력 문자열의 모든 문자를 검사하고, stack에 원소가 남아있다면 원소를 string으로 바꿔 출력한다. 없다면, 'FRULA'를 출력한다.

풀이

BOJ 9935 문자열 폭발
1
2
3
4
5
6
7
8
9
import sys
s = sys.stdin.readline().strip()
bomb = sys.stdin.readline().strip()
stack = []
for i in range(len(s)):
    stack.append(s[i])
    if stack[-1] == bomb[-1] and ''.join(stack[-len(bomb):]) == bomb:
        del stack[-len(bomb):]
print('FRULA' if len(stack) == 0 else ''.join(stack))