9935. 문자열 폭발

 

문제 풀이

괄호 문제와 비슷한 방식이다.

문자열을 순회하며 특정 패턴 문자열이 있을 때 제거하고, 변형된 문자열로 계속해서 반복 연산하는 문제이다.

 

⭐ [문자 추가] -> [조건 검사] -> [패턴 찾아 제거]

1. base 문자열을 순회하며 스택에 각 문자(c)를 넣는다.

2. 스택의 크기가 sub 문자열의 개수보다 작으면 같은 길이의 문자열 비교가 불가하므로, 다음 반복으로 넘어간다(continue 사용)

2. sub 문자열과 스택의 끝에서 sub 문자열의 길이만큼 슬라이싱한 문자열을 비교하여 같다면 제거한다. (del 사용)

 

# 문자열 폭발
import sys

input = sys.stdin.readline

def solution(base, sub):
    sub_len = len(sub)
    stack = []

    for c in base:
        stack.append(c) # 문자열 넣기
        if len(stack) < sub_len: # 스택에 저장된 문자열의 개수가 더 적은 경우 
            continue
        else:
            if stack[-sub_len:] == sub: # sub 문자열과 스택을 비교하여 같다면
                del stack[-sub_len:]

    return ''.join(stack) if stack else "FRULA"

# 입력
base = list(input().strip())
sub = list(input().strip())
print(solution(base, sub))

 

 

정리

골드 3 ~ 5 까지의 스택문제는 이런 유형이 많은 것같다. 

문자열을 순회하며 특정 패턴을 찾아 제거하고, 그 결과로 변형된 문자열에 대해 같은 작업을 반복하는 유형이다. 

비슷한 문제로는 백준 16120. PPAP 문제가 있다.