스택 테크닉 익히기1 -문자열 폭발

1. 문제

 

9935번: 문자열 폭발 (acmicpc.net)

9935번: 문자열 폭발

 

2. 풀이1

 

주어진 첫번째 문자열에서 제시된 두번째 문자열을 모두 지우고 합친다음에, 또 두번째 문자열이 존재한다면 지우고 합쳐서...

 

이를 반복해서 더이상 지울 문자열이 존재하지 않으면 그것을 출력하면 되는 간단한 문제

 

단순히 replace 함수를 사용하면 그냥 시간초과다

 

replace 함수가 O(N)보다 조금 더 걸린다고 함

 

from sys import stdin

s1 = stdin.readline().rstrip()

burst = stdin.readline().rstrip()

while 1:
    
    s2 = s1.replace(burst,'')

    if s2 == s1:
        
        s1 = s2
        break

    else:

        s1 = s2

if s1 == '':
    
    print('FRULA')

else:
    
    print(s1)

 

stack을 잘 이용하면 O(N)에 해결할 수가 있다

 

어떻게 할 수 있을까

 

첫번째 문자열을 문자 하나씩 순회하겠지

 

그 문자가 폭발시킬 두번째 문자열에 존재하지 않으면 스택에 일단 넣고보겠지??

 

근데 존재한다면... 다른 스택에 넣어줄까?

 

예시가 mirkovC4nizCC44이고 폭발시킬 문자열이 C4인데

 

m,i,r,k,o,v를 스택에 넣다가 C가 나오면... 다른 스택에 넣어주는거지

 

이렇게 접근하면 문제가 C가 나오면 다른 스택에 넣는건 좋았는데 CC44구간에서 C를 넣다가 또 C가 나오면 어떻게함??

 

그리고 C가 먼저 나오면 다행이겠지만 4가 먼저나온다면?? 

 

그리고 C가 나오다가 다음에 바로 4가 나오면 좋겠지만.. Cassfqwesd4식으로 되어가지고 C 다음에 4가 안나온다면?? 

 

이런 경우를 한방에 처리할 알고리즘의 핵심은 일단 stack에 push하다가

 

넣은 문자가 폭발시킬 문자열의 마지막 문자와 같다면...

 

stack에 폭발시켜야하는 문자열이 들어가있을 가능성이 존재하게 된다

 

그래서 stack에서 pop하는 과정을 수행한다

 

from sys import stdin

s = stdin.readline().rstrip()
burst = stdin.readline().rstrip()

len_b = len(burst)

stack = []

for char in s:
    
    stack.append(char)
    
    if char == burst[-1]:
        
        temp = []

        for j in range(len_b-1,-1,-1):
            
            boom = stack.pop()

 

그러면 stack에서 pop을 하다가 폭발시킬 두번째 문자열과 같은지 비교하는 과정을 수행해야겠지

 

m,i,r,k,o,v,C,4가 들어가다가... 4가 C4의 마지막 문자니까

 

4부터 빼기 시작해서 m,i,r,k,o,v가 남은거지

 

하지만 거꾸로 비교를 수행해서... 같다면 상관없겠지만 만약에 문자가 다르다면??

 

그거는 폭발시킬 문자열이 아니라는 뜻이지

 

예를 들어 m,i,r,k,o,v,C,a,b,c,s,d,s,w,e,4까지 들어갔는데.. 4는 C4의 마지막이니까 

 

4부터 빼기 시작했는데... 4,e가 C와 다르니까 이거는 폭발시킬 문자열이 들어간게 아니지

 

그러면 스택에 현재 m,i,r,k,o,v,C,a,b,c,s,d,s,w 이렇게 남아있는데

 

다시 e,4를 차례대로 넣어줘야겠지

 

        for j in range(len_b-1,-1,-1):
            
            boom = stack.pop()

            if boom == burst[j]:
                
                temp.append(boom)
            
            else:
                
                stack.append(boom)

                while temp:
                    
                    stack.append(temp.pop())
                
                break

 

 

그러면 모든 과정이 끝났을때 stack이 비어있으면 모든 문자열이 사라진거고.. 남아있으면 합쳐서 문자열로 만들면 끝

 

하지만 이렇게 한다면 주어진 문자열과 폭발시킬 문자열이랑 서로 같다면 에러가 난다

 

예를 들어 111, 111이면 에러가 난다

 

첫번째 문자 1이 폭발시킬 문자열의 마지막 1과 서로 같으니까

 

1 하나만 들어가도 pop과정을 수행해버리거든

 

이런 에러를 처리하는 하나의 방법은 stack에 들어가는 문자의 개수를 push할때마다 증가시켜서...

 

stack에 들어간 문자의 개수가 폭발시킬 문자열의 길이보다 크거나 같을때 pop과정을 수행하게 한다

 

from sys import stdin

s = stdin.readline().rstrip()
burst = stdin.readline().rstrip()

len_b = len(burst)

stack = []

len_s = 0

for char in s:
    
    stack.append(char)
    len_s += 1
    
    if char == burst[-1] and len_s >= len_b:
        
        temp = []

        for j in range(len_b-1,-1,-1):
            
            boom = stack.pop()
            len_s -= 1

            if boom == burst[j]:
                
                temp.append(boom)
            
            else:
                
                stack.append(boom)
                len_s += 1

                while temp:
                    
                    stack.append(temp.pop())
                    len_s += 1
                
                break
            
if stack == []:
    
    print('FRULA')

else:
    
    print(''.join(stack))

 

 

3. 최적화된 풀이

 

빠르게 구현한 풀이를 보니까 일단 문제의 핵심은 잘 파악한것 같음

 

"폭발시킬 문자열의 마지막 문자가 들어갔을때 POP과정을 수행"

 

스킬이 조금 부족했을뿐

 

마지막 문자가 들어갔을때, stack에서 폭발시킬 문자열과 같은 길이의 문자열을 한번에 뽑아내는 방법이

 

stack[-len_b:]이다

 

 

그래서 마지막 문자가 들어갔을때 stack[-len_b:]로 폭발시킬 문자열 길이만큼 slicing하고, 문자열로 바꿔서

 

폭발시킬 문자열과 같은지 비교한다음에, 서로 같다면 pop으로 전부 제거하면 된다

 

연산량이 줄어들어서 시간이 절반정도 줄어듦

 

from sys import stdin

s = stdin.readline().rstrip()
burst = stdin.readline().rstrip()

len_b = len(burst)

stack = []

for char in s:
    
    stack.append(char)
    
    if char == burst[-1]:
        
        if burst == ''.join(stack[-len_b:]):
            
            for _ in range(len_b):
            
                stack.pop()
            
if stack == []:
    
    print('FRULA')

else:
    
    print(''.join(stack))

 

 

위에서 for문 + pop을 del stack[-len_b:]로 하면 조금 더 빨라짐..

 

길이가 엄청 길면 for문 + pop이랑 비슷할것 같긴한데..

 

from sys import stdin

s = stdin.readline().rstrip()
burst = stdin.readline().rstrip()

len_b = len(burst)

stack = []

for char in s:
    
    stack.append(char)
    
    if char == burst[-1]:
        
        if burst == ''.join(stack[-len_b:]):
            
            del stack[-len_b:]
            
if stack == []:
    
    print('FRULA')

else:
    
    print(''.join(stack))