[백준/Python] 9935번(구현)_문자열 폭발

📌문제 유형

자료구조, 문자열, 스택

 

📌문제

9935번: 문자열 폭발

 

 

📌나의 문제풀이

- 시간 초과로 실패

import sys
from collections import deque

input_ = sys.stdin.readline()
check = list(sys.stdin.readline())
q = deque(input_)

while True:
    if check[0] not in q or len(q) < len(check):
        break

    word = q.popleft()

    if word != check[0]:
        q.append(word)
    else:
        flag = -1
        if len(q) > 0:
            for i in range(1,len(check)):
                if check[i] == q[i-1]:
                    flag = 0
                else:
                    flag = 1
                    break
        if flag == 0:
            q = list(q)[len(check)-1:]
            q = deque(q)
        else:
            q.append(word)

if len(q) > 0:
    print(''.join(q))
else:
    print('FRULA')

 

📌다른사람의 문제풀이

import sys
x = list(sys.stdin.readline().strip())
M = list(sys.stdin.readline().strip())
m = len(M)
stack = []

for i in x:
    stack.append(i)
    if stack[len(stack)-m:len(stack)] == M: #스택의 끝부터 M의 글자열 크기까지 자른게 M과 같다면
        for _ in range(m): # m의 길이만큼
            stack.pop() # stack에서 꺼내준다!
            
if stack:
    print(*stack, sep='')
else:
    print("FRULA")
# 출처: https://edder773.tistory.com/26 [개발하는 차리의 공부 일기:티스토리]

 

📌리뷰

- deque 쓰지도 않고 list에서 stack 구현

- 풀이가 너무 간단해서 황당

- 문자열 길이 100만이라 시간복잡도 줄이는게 포인트! (문자열 제거는 스택을 생각해보자)