[#9935] 문자열 폭발

RookieAND·2022년 11월 28일

문자열 백준 스택 코테

BaekJoon

목록 보기

37/42

❓ Question

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

📖 Before Start

스택 자료구조를 활용하여 문자열을 처리하는 방식을 채택했다.

이번 문제는 스택 자료구조를 활용하여 문자열을 처리하는 방식이었다.
문자열과 스택의 활용은 내게 어려운 문제라서 설계에 신중을 가했다.

✒️ Design Algorithm

폭발 문자열이 만들어지는 순간을 체크해서, 이를 제거해버리자.

첫째 줄에 문자열이 주어진다. 문자열의 길이는 1 이상 1,000,000 이하다.
둘째 줄에 폭발 문자열이 주어진다. 문자열의 길이는 1 이상 36 이하다.
입력으로 주어진 두 문자열은 알파벳 소문자와 대문자, 숫자로만 이루어져 있다.

그렇다면 문자열을 하나씩 스택에 집어넣으면서, 폭발 문자열이 만들어지는 순간을
조건으로 파악하여 이를 순차적으로 제거하는 방식이면 어떨까? 하는 생각이 들었다.

폭발 문자열이 만들어지는 조건은 아래와 같다.

현재 스택에 쌓인 문자열의 길이가 폭발 문자열의 길이보다 같거나 클 때.
가장 최근에 스택에 추가된 문자가 폭발 문자열의 마지막 문자와 같을 때.
스택의 최상단에서 문자열을 만들 경우, 폭발 문자열의 내용과 동일할 때.

💻 Making Own Code

❌ Wrong Code

import sys

read = sys.stdin.readline
sentence = read().rstrip()
boom = list(read().rstrip())

stack = []
for word in sentence:
    stack.append(word)
    if len(stack) >= len(boom) and word == boom[-1] and stack[-len(boom):] == boom:
        stack = stack[:-len(boom)]
sentence = "".join(stack)
print('FRULA' if not sentence else sentence)

방법은 좋았다만, 스택에서 폭발 문자열을 제거하는 과정이 문제였다.

테스트 케이스에서는 문제 없이 결과가 잘 나왔지만, 시간 초과가 나오고 말았다.

원인은 stack 에서 폭발 문자열을 제거한 나머지 list 를 재할당하는 것이었다.
문자열의 길이가 최대 1,000,000 까지다 보니, 이러한 방식은 많은 시간을 소요한다.

따라서 새로운 list 를 재할당하는 방식에서, del 키워드를 사용하는 것으로 선회했다.

✅ Correct Code

import sys

read = sys.stdin.readline
sentence = read().rstrip()
boom = list(read().rstrip())

stack = []
for word in sentence:
    stack.append(word)
    if len(stack) >= len(boom) and word == boom[-1] and stack[-len(boom):] == boom:
        # del 키워드를 사용하여 스택에서 폭발 문자열 제거.
        del stack[-len(boom):]
sentence = "".join(stack)
print('FRULA' if not sentence else sentence)