폭발 문자열

문제 설명

상근이는 문자열에 폭발 문자열을 심어 놓았다. 폭발 문자열이 폭발하면 그 문자는 문자열에서 사라지며, 남은 문자열은 합쳐지게 된다.

폭발은 다음과 같은 과정으로 진행된다.

• 문자열이 폭발 문자열을 포함하고 있는 경우에, 모든 폭발 문자열이 폭발하게 된다. 남은 문자열을 순서대로 이어 붙여 새로운 문자열을 만든다.
• 새로 생긴 문자열에 폭발 문자열이 포함되어 있을 수도 있다.
• 폭발은 폭발 문자열이 문자열에 없을 때까지 계속된다.

상근이는 모든 폭발이 끝난 후에 어떤 문자열이 남는지 구해보려고 한다. 남아있는 문자가 없는 경우가 있다. 이때는 "FRULA"를 출력한다.

폭발 문자열은 같은 문자를 두 개 이상 포함하지 않는다.

입력

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1보다 크거나 같고, 1,000,000보다 작거나 같다.

둘째 줄에 폭발 문자열이 주어진다. 길이는 1보다 크거나 같고, 36보다 작거나 같다.

두 문자열은 모두 알파벳 소문자와 대문자, 숫자 0, 1, ..., 9로만 이루어져 있다.

출력

첫째 줄에 모든 폭발이 끝난 후 남은 문자열을 출력한다.

전체 코드

string=input()
explode=list(input())

stack=[]
length=len(explode)
for i in range(len(string)):
    stack.append(string[i])
		#스택의 top과 폭발 문자열 맨 끝 문자열이 일치한다면,
    if stack[-1]==explode[-1]:
				#스택의 탑에서부터 거꾸로 확인해본 결과, 폭발 문자열과 일치한다면,
        if stack[-length:]==explode:
						#스택에서 없앤다.
            del stack[-length:]

if len(stack)>0:
    print("".join(stack))
else:
    print("FRULA")

해설

문자열 일치 문제는 문자열의 끝에 집중해야 한다.

문자열의 처음부터 확인하는 것보다는, 끝이 일치하는지 먼저 확인한 다음 그 이전의 문자열들도 같은 지 확인하는 것이 효율적이다. 왜냐하면 처음부터 확인할 경우, 중간에 하나라도 다르면 괜히 탐색한 것이 되기 때문이다.

문자열의 끝을 확인하는 데 효율적인 자료구조는 스택이다. 스택의 탑만 확인하면 문자열의 끝이 무엇인지 바로 알 수 있기 때문이다.

그림으로 과정을 표현하면 다음과 같다.

1. 문자열을 스택에 넣다가, stack의 탑이 폭발 문자열의 끝과 일치하는 지 확인한다.
   

2. 일치한다면, 폭발 문자열의 길이만큼 확인해본다. 같으면 del stack[-len(explode):]로 지운다.
   

지운 결과는 다음과 같다.

시간 복잡도 확인하기

원래라면 pop을 반복하는 것이 del [a:b]보다 빠른 것이 일반적이다. 왜냐하면 del [a:b]를 하게 되면 자른 만큼 한 칸씩 배열을 땡겨야 하기 때문이다. 하지만, 이 문제에서는 다르다.

이 문제에서는 del [-len(explode):] 이므로 스택의 탑에서부터 거꾸로 해서 폭발 문자열의 길이만큼 잘라낸다.
스택의 탑까지 전부 잘라내는 것이기 때문에 한 칸씩 땡길 필요가 없다. 따라서 이 경우에는 O(N)이 아닌 O(1)이였다.