[백준/BOJ] 9935번 : 문자열 폭발 _Python

9935번: 문자열 폭발

 

>문제

>접근방법

   insert나 replace를 이용하면 시간초과가 나온다. 대신 스택을 이용해서 한 글자씩 스택에 넣고 폭발문자열이 있으면 pop을 해주는 방식으로 푼다.

 

 

>풀이법

   1. 입력받은 문자열을 스택에 하나씩 append 할때마다 폭발문자열과 비교한다.

   2. 폭발 문자열의 길이만큼 스택의 크기가 길어지면

   3. 스택과 폭발문자열 각각 끝부분부터 비교한다.

   4. 폭발문자열의 길이만큼 전부 같으면 그 길이만큼 pop 해준다. (폭발 문자열 제거)

 

 

>코드

ch = list(input())
boom = list(input())
blen, clen = len(boom), len(ch)
out = []

for i in range(clen):
    out.append(ch[i])  
    
    if blen <= len(out):
        term = 0
        for j in range(blen):
            if out[-(j+1)] != boom[-(j+1)]:
                break
            else:
                term += 1
        if term == blen:
            for _ in range(blen):
                out.pop()

# if len(out) != 0:
#     print(''.join(out))
# else:
#     print("FRULA")

print(''.join(out)or"FRULA")

 

 

>결과

 

>결론 

만만치 않았던 골드문제