[문자열/백준] 9953번 : 문자열 폭발

- 문제 : https://www.acmicpc.net/problem/9935

 

문제 이해 

- 문제를 이해하는데는 그렇게 어렵지 않은데, 시간초과가 발생했어서 좀 어려웠던 문제다.

- 첫번째 문자열과 두번째 문자열이 주어지는데, 두번째 문자열이 첫번째 문자열에서 없어질 때까지 반복한 뒤 남은 문자열을 출력하는 문제다. 

- 처음에는 문자열 인덱싱으로 풀어보려했으나, 그러면 문자열 탐색이 계속 진행돼서 시간초과가 발생했다.

- 해결책은 스택을 이용하는 것인데, 정답을 출력하는 stack을 만들어 놓고, 오른쪽 끝에서 두번째 문자열 길이(n)의 문자열이 두번째 문자열과 동일하다면 stack에서 n번만큼 pop을 하는 방법이다. 

- 스택으로 풀어야 한다고 해서 첫번째 문자열에 stack을 사용한다고 생각했는데, 정답으로 출력한 배열을 stack으로 진행하면 되는 것을 배운 문제다. 

 

정답 풀이 

string = input()
target = input()
n = len(target)

stack = []

for i in range(len(string)):
    stack.append(string[i])
    if ''.join(stack[-n:]) == target:
        for _ in range(n):
            stack.pop()
            
if stack:
    print(''.join(stack))
else:
    print('FRULA')