[Python] 백준 9935번 문자열 폭발

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

 

풀이

string 내장함수 partition을 사용하면 문제를 쉽게 해결 할 수 있으나 string 범위가 1000000 이므로 시간초과가 발생합니다.

따라서 stack구조를 사용해 한번의 반복문으로 해결합니다.

stack의 폭발문자열의 길이에 해당하는 마지막 문자열을 검사하여, 폭발문자열이라면 stack에서 pop 해줍니다.

string = input()
exp = input()
ex_len = len(exp)
# while True:
#     s = string.partition(exp)
#     if s[1] == '':
#         break
#     string = str(s[0]) + str(s[2])

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

stack = []
for i in range(len(string)):
    stack.append(string[i])
    if ''.join(stack[-ex_len:]) == exp:
        for _ in range(ex_len):
            stack.pop()

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