백준 - 9935 문자열 폭발

문제

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

풀이

전체적인 접근

만약 시간제한이 없다면, 파이썬 내장함수로 해결이 가능한 매우 쉬운문제, 하지만 시간이 상당히 적게 주어진다. 그렇기 때문에 시간관리를 하면서 문제에 접근을 해야한다.
예제의 입력으로는 문자열, 폭탄문자열이 주어지는데 이 폭탄 문자열들을 지워서 최종적으로 나오는 결과물을 출력해주면 된다. 만약 결과물이 없다면 FRULA 라고 출력해주면 된다.

잘못된 방법

처음 이 문제를 접근 할 때는 파이썬에서 제공하는 문자열 내장함수를 이용하여 문제에 접근했었다.

import sys
input_str = sys.stdin.readline().rstrip()
boom = sys.stdin.readline().rstrip()

while boom in input_str:
    input_str = input_str.split(boom)
    input_str = ''.join(input_str)

if input_str == '':
    print("FRULA")
else:
    print(input_str)

그 결과는 당연히 시간 초과였고, 시간 복잡도 분석을 해보면 input_str을 지속적으로 선형 반복을 수행하기 때문에 while문은 대략 O(N)이 소요될 것으로 보인다.
while문 내부에서는 split, join 내장함수가 실행되는데 split 함수의 경우 O(N)이 소요, join 또한 O(N)이 소요될 것으로 보인다 따라서 위의 소스코드는 O(N^2)가 소요되는 것으로 보인다.

올바른 방법

위의 접근 방법에서는 O(N^2)가 소요되었으나 시간초과가 나타나게되었다. 그렇다면 O(N^2)보다 더 향상된 속도가 필요하다. 여기서 더 빠른 속도를 구현하기 위해서는 O(N)의 속도가 필요할 것이다. 그렇다면 문자를 하나씩 넣을때마다 끝에서 폭발 문자열의 길이만큼 조사하여 폭탄 문자라면 그 부분만 제거하면 O(N)의 속도가 나올 것으로 예상된다.

import sys
input_str = sys.stdin.readline().rstrip()
boom = sys.stdin.readline().rstrip()

result = []
for idx in range(len(input_str)):
    result.append(input_str[idx])
    if len(input_str) >= len(boom):
        if ''.join(result[-(len(boom)):]) == boom:
            for i in range(len(boom)):
                result.pop()

print(''.join(result) if result else "FRULA")

해당 소스코드에서도 for문이 이중으로 돌아가나 폭발 문자열의 경우 최대 문자열 길이가 36이기 때문에 처음으로 주어지는 문자열의 길이인 100만보다 비교가 무의미한 차이이므로 신경쓰지 않는다.
따라서 O(N)의 속도로 문제를 해결 할 수 있다.