[백준] 9935 파이썬 - 문자열 폭발

문제

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

 

첫 풀이 코드

import sys
input = sys.stdin.readline

str = input().strip()
explosion_str = input().strip()

def check_explosion(str):
    # 시간초과
    # new_str = "".join(str.split(explosion_str))
    new_str = str.replace(explosion_str,"")
    return new_str

def solution():
    global str
    while(True):
        # 문자열이 폭발 문자열을 포함하지 않는 경우 break
        if explosion_str not in str:
            break
        str = check_explosion(str)
    
    if str != '':
        print(str)
    else:
        print("FRULA")

solution()

 

처음엔 폭발 문자열을 제거할 때 Join과 Split을 활용하여 하나의 explosion_str만 제거했다.

해당 코드가 시간초과가 나서 

두번째에는 replace를 통해 여러개의 explosion_str을 한 번에 제거해주었다.

그러나 둘 다 시간초과가 나서 다른 방법을 고민해보게 되었다. .

 

최종 코드

import sys
input = sys.stdin.readline

str = input().strip()
explosion_str = input().strip()

def check_explosion(str):
    stack = []

    for i in str:
        stack.append(i)
        # 스택의 마지막 explosion_str 길이만큼의 문자열이 explosion_str과 같은 경우
        if "".join(stack[-len(explosion_str):]) == explosion_str:
            for _ in range(len(explosion_str)):
                stack.pop()

    return "".join(stack)

def solution():
    global str
    str = check_explosion(str)
    
    if str != '':
        print(str)
    else:
        print("FRULA")

solution()

 

stack을 활용하여 시간복잡도를 O(N)으로 줄여야만 풀 수 있는 문제였다.

문자열 문제를 푼지 너무 오래되서 하나 골라봤는데.. 오랜만에 푸니까 생각보다 어려웠다.

오늘 남은 2문제도 문자열로 풀어야겟어