[알고리즘] 문자열 폭발 - 구현

1. 문제

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

 

 

2. 풀이

1. 문제의 핵심은 시간복잡도!

 

2. 실패코드

- 기본적인 slicing을 통해 코드를 구할 수 있음

- n의 범위를 따질 때, O(n * ( n - len(boom) ) + slicing으로 나오는 시간복잡도. => 기준 초과

=> 1%에서 시간초과가 난다

 

3. 성공코드

- stack에 담아가며 stack의 길이가 len(boom)이상이며, stack[-len(boom):] 이 boom이랑 같을때마다 pop()

-> O(N)의 시간복잡도를 갖는다는 걸 알 수 있다.

 

3. 코드

1. 시간 초과 코드

string = input()
boom = input()

b = len(boom)

while True:

    flag = False

    if string == "":
        print("FRULA")
        break

    for i in range(len(string)-b+1):
        if string[i:i+b] == boom:
            string = string[:i] + string[i+b:]
            flag = True
            break
    
    if not flag:
        print(string)
        break

 

 

2. 성공 코드

string = input()
boom = input()

b = len(boom)
st = []

for i in string:
    st.append(i)

    if len(st) >= b and ''.join(st[-b:]) == boom:
        for _ in range(b):
            st.pop()

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