9935번 - 문자열 폭발

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

9935번: 문자열 폭발

이 문제를 풀기 위해 처음 떠올린 알고리즘은 쉬웠다. 파이썬의 리스트 index 함수를 사용하여 일치하는 값이 있으면 해당 인덱스부터 폭발 문자열의 길이만큼 요소를 삭제한 후에 새로운 string을 복사하여 폭발열과 일치하는 문자열이 없을 때까지 반복했다.

# 문자열 폭발
import sys
input = sys.stdin.readline

string = input().rstrip()
bomb = input().rstrip()

while True:
    if bomb in string:
        idx = string.index(bomb)
        string = string[:idx] + string[idx+len(bomb):]
    else:
        break

if string == '':
    print('FRULA')
else:
    print(string)

하지만 이 방법은 폭발 문자열을 발견할 때마다 새로운 string을 만들기 때문에 시간 초과가 발생하였다.

두 번째로 생각한 방식은 stack을 사용하는 것이었다. 스택에 문자를 하나씩 넣다가 폭발 문자열의 마지막 글자와 같은 글자가 있다면 리스트 슬라이싱을 통해 폭발 문자열과 동일한지 비교한 후, 같다면 폭발 문자열의 길이만큼 스택에서 pop 연산을 통해 제거해주었다. 하지만 이 또한 시간 초과가 발생하였다.

# 문자열 폭발
import sys
input = sys.stdin.readline

string = input().rstrip()
bomb = input().rstrip()

stack = []
for idx in range(0, len(string)):
    stack.append(string[idx])
    if string[idx] == bomb[-1]:
        if ''.join(stack[::-1][:len(bomb)]) == bomb[::-1]:
            for i in range(len(bomb)):
                stack.pop()

if len(stack) == 0:
    print('FRULA')
else:
    print(''.join(stack))

발생한 원인은 리스트 인덱싱을 비효율적으로 하였기 때문이다. 역순으로 바꾼 후에 거기서 폭탄 문자열의 길이만큼 가져오기 때문에, O(N)이라는 리스트의 요소를 가지고 오는 연산을 두 번이나 수행한다. 따라서 시간 초과가 발생한 것 같다. 

# 문자열 폭발
import sys
input = sys.stdin.readline

string = input().rstrip()
bomb = input().rstrip()

stack = []
for idx in range(0, len(string)):
    s = string[idx]
    stack.append(s)
    if s == bomb[-1]:
        if ''.join(stack[-len(bomb):]) == bomb:
            for i in range(len(bomb)):
                stack.pop()

if len(stack) == 0:
    print('FRULA')
else:
    print(''.join(stack))

최종적으로 제출한 답안은 위와 같다. 이전 방법보다 효율적으로 stack에 접근하고 있다.

시간초과 없이 통과할 수 있었다.