[Baekjoon] 9935번 : 문자열 폭발 (Python, 문자열)

[Baekjoon] 9935번 : 문자열 폭발 (Python, 문자열)

 

목차

  
• 코드 링크
• Python
  • 시간 초과 - 방법 1 - 코드 길이 238B
  • 방법 2 - 메모리 42020KB / 시간 832ms / 코드 길이 228B

 

 

 

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

9935번: 문자열 폭발

코드 링크

https://github.com/stellaluminary/Baekjoon

GitHub - stellaluminary/Baekjoon

 

Python

 

시간 초과 - 방법 1 - 코드 길이 238B

 

만약 폭발 문자열이 문자열 내에 있으면 ''공백으로 만드는 replace를 활용하였지만 시간 초과

$O(N^2)$

 

import sys
input = sys.stdin.readline

n = input().rstrip()
m = input().rstrip()

while 1:
    if m in n:
        n = n.replace(m,'')
    else:
        if len(n):
            print(n)
        else:
            print('FRULA')
        break

 

방법 2 - 메모리 42020KB / 시간 832ms / 코드 길이 228B

 

방법 1에서의 시간 복잡도는 $O(N^2)$이다.

반면 stack을 활용한 단순 비교는 $O(N)$이다.

이를 통해 시간 초과를 해결할 수 있다.

 

n = input()
m = input()

stack = []

for c in n:
    stack.append(c)
    if c == stack[-1] and ''.join(stack[-len(m):]) == m:
        del stack[-len(m):]

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