[BOJ] 9935 문자열 폭발

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

문제 요약

• 문자열과 폭발 문자열이 주어진다.
• 문자열안에 폭발 문자열이 포함된 경우, 폭발하여 사라지고 그 외에 영역은 합쳐져 새로운 문자열을 구성한다.
• 새로 구성된 문자열 안에 반복적으로 폭발 문자열이 포함될 수 있다.
• 폭발이 끝난 후 문자열을 출력한다.

접근

• 직관적으로 접근할 수 있는 방법의 한계
  • 기존 문자열 s에서 폭발 문자열을 포함하는 index를 구한 후, 폭발 문자열을 제외한 문자열을 새로운 문자열 s로 구성하면 쉽다.
  • 하지만 매번 폭발 후 0번째 index부터 폭발 문자열이 있는 n번에 순차적으로 접근해서 위치를 찾아야하기 때문에 시간초과가 발생한다.
• 스택을 이용하면 처음 위치부터 탐색하지 않기 때문에 좋은 성능으로 구현할 수 있다.
  • 새로운 변수에 기존 문자열 s를 순차적으로 추가하다가 폭발 문자열의 마지막 문자와 같으면 폭발 문자열의 길이만큼 추가된 문자열을 비교한다.

  if len(answer)>=bomb_len: # 추가된 폭발 문자열보다 크거나 같을때
       if answer[-1]==bomb_s[-1]:
           compare_s=''.join(answer[-bomb_len:]) # 추가된 문자열에서 폭발 문자열의 길이만큼 뒤에서 접근

  • 최근 추가된 문자들이 폭발 문자열과 일치할 경우 폭발 문자열의 길이 만큼 pop()을 수행한다.

코드

s=input()
bomb_s=input()
bomb_len=len(bomb_s)
answer=[]

for i in s:
    answer.append(i)
    if len(answer)>=bomb_len: # 추가된 폭발 문자열보다 크거나 같을때
        if answer[-1]==bomb_s[-1]:
            compare_s=''.join(answer[-bomb_len:]) # 추가된 문자열에서 폭발 문자열의 길이만큼 뒤에서 접근
            if compare_s==bomb_s:
                for j in range(bomb_len):
                    answer.pop()
print(''.join(answer)) if len(answer)!=0 else print('FRULA')