[백준] 문자열 폭발 (문자열) 🥇

문제보기

🔑 문제 해결 과정

1) len(폭발문자열) <= len(현재 문자열): 을 만족하면, 폭발 문자열 == 현재 문자열을 만족하는지 비교해준다.

• 1)을 만족하지 않으면, 문자열을 계속해서 추가시켜준다. 자료구조는 stack을 이용했다.

2) 문자열을 비교하기 위해서, start와 end 포인터를 선언하고, 문자열이 하나씩 새로 stack에 들어올때마다, start += 1을 해준다.

3) stack에 하나씩 추가한 문자열에 폭발 문자열이 발견된다면, 폭발 문자열의 길이만큼 stack.pop()을 해준다.

⚾ 시간 복잡도

폭발문자열 길이만큼 비교하기 때문에 O(n) , 이 때, n <= 36
삭제할 문자열의 수 O(n), n <= 1,000,000

✏️ python 코드

s = str(input())
bomb = str(input())
stack = []
# 시작 포인터
start = 0
# 끝 포인터
end = len(s) - 1
while (start <= end):
    ck = True
    stack.append(s[start])
    start += 1 # 시작 포인터 한 칸 앞으로 이동
    if len(stack) >= len(bomb):
        for i in range(len(bomb)):
            if bomb[i] != stack[len(stack) - len(bomb) + i]:
                ck = False
                break
        if ck == True:
            for i in range(len(bomb)):
                stack.pop()
if len(stack) == 0:
    print("FRULA")
else:
    for i in range(len(stack)):
        print(stack[i], end='')