[백준][python]9935 문자열 폭팔

문제

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

소스코드

import sys
input = sys.stdin.readline
if __name__ == "__main__":
    a,b = [input().rstrip() for _ in range(2)]
    stack = []

    for i in a:
        stack.append(i)
        if len(stack) >= len(b):
                tmp = ''.join(stack[-len(b):])
                if tmp == b:
                    for _ in range(len(b)):
                        stack.pop()
    print('FRULA' if len(stack) == 0 else ''.join(stack))

설명

이 문제는 직접 문자열을 하나씩 제거하는 문제가 아니다. 하나씩 문자열을 제거하게 된다면 문자열을 아주 여러번 생성하게 되어 시간초과가 발생한다.

이를 해결하기 위해 문자열을 매번 생성하려는 접근이 아닌 스택을 만들어서 폭팔 문자를 제거하면 된다.

1. 원본 문자열과 폭팔 문자열을 입력받는다.
2. 스택을 선언한다.
3. 원본 문자열을 스택에 하나씩 넣으면서 반복문을 실행한다.
   1. 스택에 담은 마지막 문자부터 폭탄문자열길이 만큼 슬라이싱해서 폭팔문자열하고 같은지 판별한다
   2. 같다면 폭팔문자열 만큼 POP 해준다.

후기

1. 첫번째 접근에서 단순하게 replace 로 제거를 했지만 44%에서 시간초과가 발생했다. replace는 시간이 오래 걸리는 작업이기 때문에 다른 방법을 생각해봤다.

    flag = False
    while 1:
        flag = False
        if boom in s:
            flag = True
            s = s.replace(boom,"")
        if not flag:
            break
    print("FRULA" if len(s) == 0 else s )

2. 문자열을 하나씩 체크하면서 폭팔문자를 체크해주고 새로운 문자열을 만들어주었다. 역시 시간초과가 발생했다.

문자열을 새로 만드는 접근 방식은 시간초과가 나는 것을 확인 후 새로운 접근법이 필요함을 깨달았다.

     s = list(input().rstrip())
     boom = input().rstrip()


     new_s = []
     old_s = s[:]

     while 1:
         if len(s) == 0:
             s = new_s[:]
             if len(new_s) == 0 or old_s == new_s:
                 break
             old_s = new_s[:]
             new_s = []


         if ''.join(s[:len(boom)]) == boom:
             for _ in range(len(boom)):
                 s.pop(0)
         else:
             new_s.append(s.pop(0))

     print("FRULA" if len(s) == 0 else  ''.join(s))