🔴 문제 개요
🚀 난이도 : GOLD 4
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
- 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
- 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다. - 상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
제한 사항
- 첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
- 둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
- 두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
🟠 Solution
문제를 요약하자면, 문자열에서 특정 문자열을 찾아 없애기를 반복해야 합니다. 가장 단순한 접근 법으로는 str.replace()를 활용하거나 re.sub()을 활용해서 폭발 문자열을 공백으로 대치하는 방법을 떠올릴 수 있습니다.
하지만 위 두 메서드의 경우 원본 문자열을 풀 스캔합니다. 즉, O(N)의 시간 복잡도를 가지므로, 폭발 문자열이 최소 길이 1로 주어질 경우 최대 1,000,000번 실행될 수 있으니 연산 횟수는 1,000,000 x 1,000,000 이상임을 알 수 있습니다. 시간 초과를 피하기는 불가능해 보이는 연산 횟수입니다.
원본 문자열의 길이가 1,000,000까지 주어지다 보니, 특정 문자열을 찾기 위해 풀 스캔이 아닌 다른 방법을 찾을 필요가 있습니다. 여기서 폭발 문자열의 최대 길이가 36임에 집중할 필요가 있습니다. 36이라는 숫자는 연산 횟수로 생각했을 때 그리 큰 수가 아니죠. 따라서 이를 활용하면 좋아보입니다.
원본 문자열에서 문자 하나씩을 stack 자료구조에 담고, stack에서 폭발 문자열 길이만큼을 pop으로 꺼내 폭발 문자열과 비교해보는 방법으로 정확히 폭발 문자열 길이만큼의 비교가 가능합니다. 복잡하게 구현하지 않고 리스트 슬라이싱의 시간복잡도가 O(K)이므로 이를 활용하겠습니다.
import sys
from collections import deque
input = sys.stdin.readline
string = deque(input().rstrip()) # 문자 하나씩을 고려하기 위해 큐로 활용
target = list(input().rstrip()) # 슬라이싱 된 리스트와 비교하기 위함
stack = []
while string:
stack.append(string.popleft())
if len(stack) < len(target):
continue
if stack[-len(target):] == target: # 뒤에서 부터 target의 길이만큼 비교
for _ in range(len(target)): # 같을 경우 제거
stack.pop()
print("FRULA" if not stack else "".join(stack))
이처럼 원본 문자열을 풀 스캔 하는 것이 아닌, 폭발 문자열의 길이만큼만 비교할 수 있다면 연산 횟수가 1,000,000 x 36으로 대폭 감소합니다. Python3가 1초에 2천 만번 연산을 수행하는 것을 생각했을 때 충분히 유효한 범위입니다. 단, 리스트 슬라이싱은 리스트를 복사해 다른 메모리 주소에 할당하므로 메모리를 조금 더 잡아먹을 수 있음에 유의해야 합니다.
🙏 문제 접근 방법 및 코드에 대한 피드백은 환영입니다!
