[Baekjoon]백준 9935 문자열 폭발(골드 4) - Python

문제설명 1

문제설명 2

문제는 간단하다 첫번째 입력받은 문자열에 두번째로 입력받은 문자열이 존재하지 않을 때까지 삭제하면 된다

예전에 이를 풀어본 적이 있긴하지만, 그때와는 조건이 다름에도 불구하고 혹시나 하여 

find함수를 통해 index를 찾고, 슬라이싱을 통해 문자열을 만드는 과정을 코드로 작성하여 제출하였다

import sys
input = sys.stdin.readline

text = input().strip()
Explosion = input().strip()

while True:
    findidx = text.find(Explosion)
    
    if findidx == -1:
        break
    
    text = text[:findidx] + text[findidx + len(Explosion):]
    
print(text)

역시나 시간초과가 발생한다 해당 문제는 스택을 사용하여 코드를 작성하면 더 빠른 시간내에 연산이 가능하다

첫번째 문자열을 스택에 하나씩 넣어주면서 두번째 문자열의 존재 여부를 확인하면 된다

두번째 문자열(Explosion)의 길이만큼 슬라이싱하여(stack[-len(Explosion):] 해당 문자열이

두번째 문자열과 동일한지 확인하면 된다 여기서 주의할 점은 두번째 문자열을 list화해서 확인하여야한다

그냥 확인하게 되면 배열과 문자열의 비교가 되므로 제대로 된 정답이 되지 않는다(무심코 넘어갔다가 10분동안 찾음)

만약 해당 문자열과 일치하다면 for문을 통해 비교 문자열의 길이만큼 stack.pop()을 해주면 된다

스택에 내용이 남아있다면 stack을, 없다면 FRULA를 출력하면 코드 작성은 끝이다

import sys
input = sys.stdin.readline

text = input().strip()
Explosion = input().strip()

stack = []
for ch in text:
    stack.append(ch)
    if stack[-len(Explosion):] == list(Explosion):
        for _ in range(len(Explosion)):
            stack.pop()
            
if stack:
    print(''.join(stack))
else:
    print('FRULA')

동적 계획법 알고리즘을 풀다가 스택을 풀어보니 비교적 쉽게 느껴지는 것 같다