(Python) 백준 9935번 문자열 폭발 - class 4
[문제 링크]
9935번 문자열 폭발
접근 방법
문자열의 길이가 100만이므로 일일이 확인하고 과정을 다시 반복하면 당연히 시간초과가 나올 것이다.(애초에 알고리즘 문제에서 특정 자료구조를 사용하지 않고 일일이 노가다 식으로 반복해서 풀이하는 경우는 없음) 따라서 특정한 자료구조를 사용해야 한다. 그래프 이론, 구현 문제가 아니고서야 학부 수준에서 생각나는 자료구조는 스택, 큐, 우선순위 큐이다. 그럼 이 자료구조를 사용해서 알고리즘을 설계해야 한다.
해결
문자열 일치문제는 일치문자열에 접두,접미사의 중복이 있어 kmp알고리즘을 사용해야 하는 경우가 아니라면 웬만하면 찾고자하는 문자열의 제일 끝에 집중해야한다. 이유는 간단하다. 문자열의 일치는 결국 문자열의 끝까지 일치해야하기 때문이다. 따라서 앞에서 비교하다가 끝이 다르면 지금까지 구한 과정이 쓸모 없는 과정이 되기 때문에 애초에 끝이 일치하는 것을 기준으로 탐색을 시작하는 것이 옳다.
- 첫 번째 문자열을 하나씩 스택에 넣는다.
- 스택에 넣으면서 폭발 문자열의 제일 끝 문자와 일치하는지 확인한다.
- 일치할 경우 스택의 top부터 폭발 문자열의 길이만큼 폭발 문자열과 비교한다.
- 폭발 문자열과 일치할 경우 스택에서 제거한다.
- 이 과정을 첫 번째 문자열이 스택에 끝까지 들어갈 때까지 반복한다.
참고1) 파이썬에서는 스택이던 큐던 컬렉션에서 deque를 사용했었는데 이 문제의 경우 스택에 넣었던 것을 꺼내지 않고 비교해야 하므로(peek과 같은 느낌) deque를 사용하면 안된다. 따라서 그냥 스택을 사용해야하는데 파이썬에서 스택은 [] 리스트로 해결하면 된다.
참고2) 문자열 일치 문제는 끝에 집중하는 스택으로 풀이, 특정 조건을 만족하는 문자열 길이 문제는 표를 만들어서 다이나믹 프로그래밍, 찾고자 하는 문자열에 접두접미일치한다면 kmp로 기억해두자.
import sys
input = sys.stdin.readline
str = input().rstrip()
bomb = list(input().rstrip())
m = len(bomb)
stack = []
for i in str:
stack.append(i) # 스택에 넣기
# 폭발 끝과 현재 스택의 끝이 일치하고
if i == bomb[-1]:
# 폭발문자열과 일치할 경우
if stack[-m:] == bomb:
del stack[-m:]
if stack:
print(*stack, sep="")
else:
print("FRULA")
