2021.12.03 BOJ 9935 문자열 폭발

[출처: 백준 온라인 저지]

문제

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다

풀이

문자열 문제를 많이 풀어보지 않아서 각잡고 풀어보려고 했는데 stack 자료구조 때문에 애먹은 문제다.. 처음에는 폭발 문자열의 각 문자를 딕셔너리에 저장하여 각 문자의 인덱스를 value값으로 넣어서 첫 번째 문자열을 스캔할때마다 그 순서를 확인하는 방법을 사용하였는데, 한참이 지나서야 문자열이 중복되어 들어오면 그 문자에 대한 value값이 초기화 된다는 것을 깨닫고 다시 시작하였다. 결국 게시판을 참고?한 결과 정말 간단한 방법이 있다는 것을 깨닫고 현타가 좀 왔던 문제이다... 로직은 굉장히 간단하다. 각 문자를 스캔하여 stack배열에 넣어주고 만약 stack의 길이가 explosive배열의 길이와 크거나 같으면 그때부터 stack배열의 뒤에서부터 explosive 배열의 길이만큼 확인을 해주는 것이다. 만약 explosive배열과 같다면 stack에서 explosive배열의 길이만큼 pop해주면 된다.

import sys
input = lambda: sys.stdin.readline().rstrip()
string = list(input())#전체 문자열
explosive = list(input())#폭발 문자열
stack = []
for i in range(len(string)):
  stack.append(string[i])
  if len(stack) >= len(explosive):
    t_stack = stack[-len(explosive):]
  if t_stack == explosive:
    cnt = 0
    while cnt < len(explosive):
      stack.pop()
      cnt += 1 
if stack:
  print(*stack, sep = '')
else: #문자열이 비어있으면 FRULA 출력
  print('FRULA')

느낀 점:

딕셔너리는 정말 유용한 자료구조지만 key값은 중복을 허용하지 않는다는 점을 망각하여 시간을 낭비하게 된 것 같다. 가끔 잔재주를 부리다보면 자기 꾀에 넘어가는 경우가 있는데 내가 딱 이 경우인 것 같다...