문제
상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.
폭발은 다음과 같은 과정으로 진행된다.
문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.
상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.
폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.
입력
첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.
둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.
두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.
출력
첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.
예제 입력 1
mirkovC4nizCC44
C4
예제 출력 1
mirkovniz
나의 풀이
- 자료구조를 적절히 활용해 시간복잡도를 낮추는 것이 핵심인 문제이다. 나의 경우 처음에 문제를 잘못 이해해 연속된 문자열이 아닌 문자열에 포함된 문자를 각각 삭제하도록 구현했다가 틀렸다. 연속된 문자열이 target과 동일해야 하므로 슬라이딩 윈도우 알고리즘으로 문자열의 처음 문자부터 가능한 범위의 문자까지 모두 순회하며 target과 비교해야 한다. 이 문제의 시간 제한은 2초이고 입력 문자열과 폭발 문자열 길이는 각각 최대 1,000,000, 36이다. 따라서 컴퓨터가 1초에 최대 10^8 번 연산한다고 가정할 때 이 문제에서 연산 가능한 횟수는 대략 2(10^8)번으로 O(NM)의 시간복잡도를 목표로 해야 한다.
- 슬라이딩 윈도우 알고리즘으로 N번 순회하며 스택에 문자열의 문자를 집어넣고 스택의 맨 윗부분의 일부가 target과 동일하면 삭제하는 것을 반복하도록 구현했다. list 함수는 객체를 순회하며 한 글자씩 리스트에 담기에 O(N)의 시간복잡도를 가지지만 아래 코드에서 target은 최대 36 문자이기에 list(target)의 연산 회수는 매우 적다. 예제 입력 1에 대한 동작 순서는 아래 그림과 같다.
import sys
stack =[]
mystr = sys.stdin.readline().strip()
target =sys.stdin.readline().strip()
for i in range(0,len(mystr)):
stack.append(mystr[i])
if len(stack)<len(target):
continue
else:
if stack[-len(target):]==list(target):
del stack[-len(target):]
if len(stack)==0:
print("FRULA",end='')
else:
print(''.join(s for s in stack),end='')
SAY CHEESE