알고리즘 유형 : 스택
풀이 참고 없이 스스로 풀었나요? : O
https://www.acmicpc.net/problem/9935
소스 코드(파이썬)
import sys
input = sys.stdin.readline
# 문자열의 어떤 부분에서 폭발 문자열을 제거하면, 그 문자열 기준 왼쪽의 문자열을 기준으로
# 오른쪽 문자열이 합쳐진다고 생각할 수 있다. 따라서 왼쪽에서 오른쪽 방향으로 하나씩
# 스택에 추가하면서, 그 때마다 스택의 맨 오른쪽 부분이 boom과 같은 문자열일 때 계속
# 제거해주면 된다.
def solution():
data = input().rstrip()
boom = input().rstrip()
stack = []
# data의 맨 왼쪽부터 문자 하나씩 스택에 추가한다.
for i in range(len(data)):
stack.append(data[i])
# 현재 스택에 담긴 문자열의 맨 오른쪽 부분이 boom과 같을 때, 스택에서 해당 문자열을 제거한다.
if stack and len(stack) >= len(boom) and ''.join(stack[-1*len(boom):]) == boom:
for j in range(len(boom)):
stack.pop()
if stack:
print(''.join(stack))
else:
print("FRULA")
return
solution()풀이 요약
-
in과 replace를 활용하기에는 문자열 길이가 100만까지라서 최악의 경우 O(N^2)까지도 소요된다.
다른 방법을 생각해보자.
-
폭발 문자열을 제거할 때, 원래 문자열에서 폭발 문자열 기준 왼쪽 부분의 문자열에 오른쪽 부분의 문자열이 합쳐지는 것으로 생각할 수 있다.
그리고 합쳐진 문자열에서 폭발 문자열이 있다면 같은 방식으로 또 지우고 합친다.
이걸 원본 문자열의 맨 왼쪽부터 오른쪽 방향으로 하나씩 탐색하면서 폭발 문자열이 나타나면 지우고, 오른쪽 방향으로 계속해서 탐색하는 식으로 생각해보자.
현재 탐색중인 문자열 부분 기준 맨 오른쪽에서 폭발 문자열을 감지 및 제거하고, 맨 오른쪽에서 이 후의 문자열을 계속 탐색해나간다. 스택의 특성과 유사하니 스택으로 풀어보자.
-
data의 맨 왼쪽부터 문자열 하나하나씩 스택에 추가해나간다. 그 각각의 순간에 대해, 스택의 맨 오른쪽 부분 문자열이 boom과 같다면 이걸 제거해준다.
참고로 제거하기 전에 먼저 스택에 값이 담겨있는지 여부와, 스택에 담겨있는 문자열이 boom보다 길이가 길거나 같은지를 검사해야한다.
스택이 비어있다면 애초에 지울 것도 없고, boom과 같은지 검사하는 부분에서 index error가 날 수 있으므로 검사해준다.
스택의 길이가 boom보다 짧다면 boom과 절대 같을 수 없고 마찬가지로 인덱스 에러 가능성이 있으므로 배제해준다.
for문을 진행하면서, 스택의 길이가 boom보다 짧은 순간은 얼마든지 여러번 발생할 수 있다. 가령 acbcb에서 cbcb를 지우면 a가 남는데 바로 이런 경우에 해당한다.
그러니 for문을 진행하는동안 매번 검사해줘야한다.
배운 점, 어려웠던 점
- 예제의 흐름을 직접 따라가보면서 스택의 특성과 유사한 부분을 찾는게 핵심이었다. 무난한 스택 문제였다.
