백준 28278번 : 스택 2

 

28278번: 스택 2

무엇이 문제일까?

왜 시간 초과일까?

숏코드를 보고싶었는데, 공개된 코드가 안보인다

n = int(input())
stack = []
for _ in range(n):
    order = list(map(int, input().split()))

    if order[0] == 1:
        stack.append(order[1])

    elif order[0] == 2:
        if stack:
            print(stack.pop())
        else:
            print(-1)

    elif order[0] == 3:
        print(len(stack))

    elif order[0] == 4:
        if stack:
            print(0)
        else:
            print(1)

    else:
        if stack:
            print(stack[-1])
        else:
            print(-1)

구글링 했을 때 나오는 방식이 다 거기서 거기였다

내 코드랑 다른게 거의 없는데

달라봐야 input 받아오는 방식이 다를 뿐

 

시간 초과가 뜨는 이유를 알고계시는 분이 있다면 제발 도움을 주세요

 

 

하. 결국 GPT를 이용해 해결했다.

일단 첫번째로 든 생각은 조건문이 너무 많은가?

이를 줄여야 하는가?

라고 생각을 해서 람다 함수를 써보고자 하였으나, 그래도 시간초과 문제가 발생했었다.

 

그래서 G선생에게 물어본 결과, 리스트를 queue처럼 사용할 때 pop 연산 시 시간복잡도가 O(n)이 된다고 한다.

pop 연산 자체가 기본이 맨 뒤의 요소를 빼내는 것인데, 맨 앞에있는 요소를 빼려고 하다보니 O(n)이 될 수밖에 없는 것이다.

 

그래서 GPT가 제안해준 방식은 deque를 활용하는 것

deque자체가 앞뒤로 빼낼 수 있는 자료구조이니 시간 효율성을 따졌을 때 queue보다 훨씬 나은 것이다.

 

뭐, deque도 queue니까!

import sys
from collections import deque

queue = deque()
n = int(sys.stdin.readline())

commands = {
    "push": lambda x: queue.append(x),
    "pop": lambda: print(queue.popleft() if queue else -1),
    "size": lambda: print(len(queue)),
    "empty": lambda: print(0 if queue else 1),
    "front": lambda: print(queue[0] if queue else -1),
    "back": lambda: print(queue[-1] if queue else -1)
}

for _ in range(n):
    cmd = sys.stdin.readline().split()
    if cmd[0] == "push":
        commands[cmd[0]](cmd[1])
    else:
        commands[cmd[0]]()