백준 9935번 문자열 폭발

이거는 2021년 05월 04일...

---

코드포스 맛만 보려고 하다가 갑자기 하루 연기되어서 작성하는 포스트

https://www.acmicpc.net/problem/9935

문자열에 폭발 문자열이 심어져있고

폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지고

남은 문자열은 합쳐진다.

폭발이 모두 끝나고 남은 문자열을 구해야하는데

모두 터져서 아무 것도 없으면 FRULA 가 나와야 한다.

ex) mirkovC4nizCC44 라는 문자열과 C4 라는 폭발 문자열이 주어지면

모든 폭발이 끝나면 남는 문자열은 mirkovniz

12ab112ab2ab / 12ab → FRULA

풀이

문자열의 앞에서부터 하나씩 스택에 넣는다.

폭발 문자열의 맨 마지막 글자와 같은 글자를 만나면 스택에서 폭발 문자열 길이만큼 꺼내서 비교해본다.

폭발 문자열과 일치하면 버려버리고 아니면 다시 넣어준다.

왜 맨 뒤 글자가 같은지 확인하나 → 앞에 글자가 일치하는 경우에 확인하게 되면 폭발 문자열 사이에 폭발 문자열이 또 끼여있을 때 굉장히 별로다. 맨뒤꺼로 하면 편안하다.

코드

from sys import stdin
from collections import deque

string = stdin.readline().rstrip()
bomb = stdin.readline().rstrip()

s = deque()

for i in string:
  if i != bomb[-1]:               # 폭발 문자열 맨뒤와 다르면 push
    s.append(i)
  else:                           # 같으면 일단 넣고
    s.append(i)                   # 폭발 문자열 길이만큼 꺼내서 비교
    temp = ''                     # 꺼내는 도중 스택이 동날 수 있으니 주의한다
    for j in range(len(bomb)):
      temp = s.pop() + temp
      if len(s)==0:
        break
    if temp != bomb:
        for k in temp:
          s.append(k)

if len(s)==0:
  print('FRULA')
else:
  ans=''
  for i in s:
    ans += i
  print(ans)

코드 자체의 작성보다는 어떻게 풀지 생각해내는게 정말 어렵다.