[백준] 문자열 폭발

https://www.acmicpc.net/problem/9935

9935번: 문자열 폭발

스택(stack)을 이용하는 문제입니다. 

 

우선 문제부터 간단하게 요약하면, 문자열이 있고, 폭탄이 주어집니다. 문자열중 폭탄에 해당하는 문자열이 있는 경우 사라집니다. 이렇게 사라진 문자열에서 또 다시 폭탄에 해당하는 문자열이 있으면 또 사라집니다. 이 과정을 반복해 남는 문자열을 만드는 문제입니다. 

 

python에서는 문자열의 find 메소드를 제공합니다. 가장 처음에는 이 방법을 시도해서 문제를 해결하려 했으나 시간초과가 남을 알 수 있었습니다. 

 

정답을 먼저 설명하고, 잘못된 풀이 또한 적도록 하겠습니다.

 

<Solution>

이 문제의 아이디어는 문자를 하나씩 넣으면서 stack의 끝쪽을 확인해서 만약 끝쪽에 폭탄이 있다면 제거하면 됩니다. 이렇게 하면, O(문자열의 길이) 의 시간 복잡도로 해결이 가능합니다. 

 

예시를 통해 확인해 봅시다.

 

ababcc라는 문자열과 폭탄 abc를 생각해봅시다.

stack = [] ... stack = [a,b,a] -> 끝의 세문자 != abc stack = [a,b,a,b] -> 끝의 세문자 != abc stack = [a,b,a,b,c] -> 끝의 세문자 = abc 이기에 제거 stack = [a,b,c] -> 끝의 세문자 = abc 이기에 제거 stack = []

이러한 과정을 통해 문제를 해결할 수 있습니다. 

 

실제 구현은 아래와 같습니다.

import sys

string = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()

stack = []
for s in string:
    stack.append(s)
    if len(stack) < len(bomb):
        continue
    # check from right
    if ''.join(stack[-len(bomb)::]) == bomb:
        for _ in range(len(bomb)):
            stack.pop()

print(''.join(stack)) if len(stack) != 0 else print('FRULA')

 

<잘못된 풀이>

python string 메소드 find를 이용한 풀이입니다. (시간초과)

import sys

string = sys.stdin.readline().rstrip()
bomb = sys.stdin.readline().rstrip()

while(1):
    index = string.find(bomb)

    if index == -1:
        if len(string) == 0:
            print('FRULA')
            break
        else:    
            print(string)
            break
    else:
        string = string[:index] + string[index+len(bomb):]