[백준/BOJ]#9935:문자열 폭발[문자열/스택/파이썬/python]

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

9935번: 문자열 폭발

 

처음에 보고 단순히 문자열 sequential search로 풀으니 시간초과가 났다!

역시 골드문제는 한큐에 풀리지 않지 

분류를 보니 스택인 걸 보고 스택으로 바꾸었는데 또 시간초과! 

반복문을 하나 줄이려면 뒤에서부터 탐색하면 된다는 걸 깨달았다.

그리고 마지막 res join문을 반복문안에서 하고 앉아있었다는 걸 깨닫구 코드를 수정하니 맞았다.

 

시간초과 코드(단순 순차탐색)

#9935_문자열 폭발
import sys
string = str(sys.stdin.readline().rstrip())
explode = str(sys.stdin.readline().rstrip())

len_ex = len(explode)
while(True):
    flag=False
    for i in range(len(string)-len_ex+1):
        if string[i:i+len_ex] == explode:
            string = string[0:i] + string[i+len_ex:]
            flag = True
    if flag==False:
        break

if len(string)==0:
    print("FRULA")
else:
    print(string)

 

정답 코드(스택사용)

#9935_문자열 폭발
import sys
string = str(sys.stdin.readline().rstrip())
explode = list(sys.stdin.readline().rstrip())

len_ex = len(explode)
stack=[]
for i in string:
    stack.append(i)
    if i==explode[-1] and explode==stack[-len_ex:]:
        for _ in range(len_ex):
            stack.pop()

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

 

질문검색 글들을 보니 replace문을 사용하신 분들도 있었다. (오 생각지못했다)

replace문도 시간적비용이 꽤 큰가보다.. 모두 시간초과에 쩔쩔매고 계셨다..

스택으로 풀으라고 한 문제는 스택으로 풀어야하나보다..^^;;