[백준] 9935. 문자열 폭발

⏱️ 소요시간

1시간 이하. 로직을 생각하는데 어렵지 않았다

📚 문제 요약

[백준] 9935. 문자열 폭발
전체 문자열과 폭발 문자열이 주어진다. 문자열이 폭발했을 때 남아있는 전체 문자열을 출력해라

📑 풀이 요약

입력받은 전체 문자열의 길이가 10^7 임을 보고 O(n)으로 탐색을 해야 한다는 것을 떠올릴 수 있다. 문자열 길이 보고 스택 냄새가 솔솔 나서 스택으로 풀었다.

1. 문자열을 순서대로 입력 받아 스택에 넣는다.
2. 현재 넣으려는 문자열이 폭발 단어의 마지막 단어라면 STOP
   2-1. 스택에서 n-1개와 폭발 단어의 첫단어~n-1번째 단어를 비교한다.
   2-2. 동일하다면? 폭발시킨다 (n-1개를 스택에서 pop)
   2-3. 동일하지 않다면? 폭발하지 않은거니까 그냥 append
   2-4. 전체 문자열을 스택에 넣고 종료
3. 스택에 남은 문자열이 없다면 FRULA 출력, 스택에 남은 문자열이 있다면 남은 문자열을 JOIN하여 출력

🌟 내가 만난 어려웠던 점

처음에 2-3 과정에서 끝문자를 append하지 않아 통과하지 않았음!

🖥️ 전체 코드

sentence = input()
word = input()

stack = []
n = len(word)
cnt = 0

for w in sentence:
    if cnt >= n-1 and w == word[-1]:
        flag = False
        for i in range(n-1): #i = 0, 1, 2 ...
            if stack[-i-1] != word[-i-2]:
                flag = True
                break
        if not flag:
            for i in range(n-1):
                stack.pop()
            cnt = cnt-(n-1)
        else:
            stack.append(w)
            
    else: #아닐 때
        stack.append(w)
        cnt += 1

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