[백준] 9935번. 문자열폭발

[백준] 9935번. 문자열폭발 바로가기

아이디어

• 처음 아이디어는 for문을 돌면서 문자열이 같은지 체크하는 방식이었다.
• 하다가 stack문제임을 깨닫고 stack에 넣어서 검사하는 방식으로 바꿨다.
  • stack에 넣은 글자가 폭발 문자열의 마지막 문자와 같으면 검사를 시작
  • for문으로 폭발 문자열 글자수만큼 검사

  # 현재 글자 == 폭발 문자열의 마지막 글자
  if string[i] == boom[-1]:
  	# 이렇게 하나씩 비교하려고 했으나 실패
    	for j in range(m):

• 여기서 생각을 조금 바꿔서 일단 stack에 다 넣고 stack의 글자수 m짜리 문자열을 폭발 문자열과 비교한다!

# stack의 m짜리 문자열 == 폭발 문자열
if ''.join(stack[-m:]) == boom:
	# m번만큼 pop()해서 없애주기 
	for _ in range(m):
    	stack.pop()

• 포인트는 stack문제는 일단 모든 원소를 stack에 넣고 검사하는 것 + 거꾸로 검사하는 것 인 것 같다 💡

시간 복잡도

• O(N * M)

코드

import sys
input = sys.stdin.readline

string = input().strip()
boom = input().strip()
n = len(string)
m = len(boom)
stack = []

for i in range(n):
	# 모든 문자열을 stack에 넣는다
    stack.append(string[i])
	
    # stack의 m짜리 문자열 == 폭발 문자열
    if ''.join(stack[-m:]) == boom:
    	
        # m번만큼 pop()해서 없애주기 
        for _ in range(m):
            stack.pop()
      
if stack:
    print(''.join(stack))
else:
    print('FRULA')