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

🔍 Problem

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

---

📰 문제풀이

• 제한 시간: 30분
• 성공 여부: 실패
• 실패 원인: stack 구조를 활용하지 않고 문자열 기능을 사용했다.

---

📃 Solving Process

1. 문제 자체는 간단했다. 폭발 문자열이 주어졌을 때, 주어진 문자열 S에 폭발 문자가 없을 때까지 문자열 S에 대한 탐색을 수행한다.
2. 처음에는 문자열 내장 함수를 사용해 예제는 다 맞췄지만, 함수들의 시간 복잡도가 각각 $O(N)$이었기 때문에 $O(N^2)$가 되어 시간 초과가 발생했다.
3. 따라서 stack 구조를 이용해 폭발 문자열을 발견했을 때, 폭발 문자열의 길이만큼 pop() 하도록 다시 구현했다.
4. 이때 제일 안쪽에 있는 for 문의 경우 폭발 문자열의 길이가 1~36으로 작아서 상수 시간 안에 처리될 수 있다.

---

💻 Code

# 초기 답안
import sys

# 입력값 처리
S = sys.stdin.readline().rstrip()
explosion_string = sys.stdin.readline().rstrip()

# 문자열 폭발 탐색
while explosion_string in S:
    S = S.replace(explosion_string, '')

# 결과 출력
if S:
    print(S)
else:
    print('FRULA')

---

# 개선 답안
import sys

# 입력값 처리
S = sys.stdin.readline().rstrip()
explosion_string = sys.stdin.readline().rstrip()

# stack으로 문자열 폭발 구현
stack = []
ex_len = len(explosion_string)

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

# 결과 출력
if stack:
    print(''.join(stack))
else:
    print('FRULA')

---

⏱ Time Complexity

• 폭발 문자열을 1 ~ 36으로 범위가 작아 제일 안쪽에 있는 for 문은 상수 시간 안에 수행될 수 있다.
• 제일 바깥쪽에 있는 for 문은 S의 길이만큼 반복한다.
• 따라서 시간 복잡도는 $O(N)$이다.

---

💾 Space Complexity

• 공간 복잡도는 S의 길이만큼 stack에 데이터가 쌓이기 때문에 $O(N)$이다.