[Python/파이썬] 백준 18258번 큐

18258번: 큐 2

문제

정수를 저장하는 큐를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여섯 가지이다.

• push X: 정수 X를 큐에 넣는 연산이다.
• pop: 큐에서 가장 앞에 있는 정수를 빼고, 그 수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 큐에 들어있는 정수의 개수를 출력한다.
• empty: 큐가 비어있으면 1, 아니면 0을 출력한다.
• front: 큐의 가장 앞에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 큐의 가장 뒤에 있는 정수를 출력한다. 만약 큐에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N (1 ≤ N ≤ 2,000,000)이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

코드

import sys
from collections import deque

stack = deque([])

def solution(cmd):
    if len(cmd) > 5:        # push
        stack.append(int(cmd.split()[1]))
    elif cmd == "pop":      # pop
        print(stack.popleft()) if stack else print(-1)
    elif cmd == "size":     # size
        print(len(stack))
    elif cmd == "empty":    # empty
        print(0) if stack else print(1)
    elif cmd == "front":    # front
        print(stack[0]) if stack else print(-1)
    elif cmd == "back":     # back
        print(stack[-1]) if stack else print(-1)
            
n = int(sys.stdin.readline())
for _ in range(n):
    cmd = sys.stdin.readline().strip()
    solution(cmd)

deque를 사용하지 않고 그냥 배열의 pop(0)를 사용해도 되나 해서 아래와 같이 해봤는데 아래의 코드는 시간초과가 난다.

import sys

stack = []

def solution(cmd):
    if len(cmd) > 5:        # push
        stack.append(int(cmd.split()[1]))
    elif cmd == "pop":      # pop
        print(stack.pop(0)) if stack else print(-1)
    elif cmd == "size":     # size
        print(len(stack))
    elif cmd == "empty":    # empty
        print(0) if stack else print(1)
    elif cmd == "front":    # front
        print(stack[0]) if stack else print(-1)
    elif cmd == "back":     # back
        print(stack[-1]) if stack else print(-1)
            
n = int(sys.stdin.readline())
for _ in range(n):
    cmd = sys.stdin.readline().strip()
    solution(cmd)

이 코드가 시간초과가 나는 이유는 파이썬의 list의 경우 pop(0)로 가장 앞의 값을 꺼낼 경우 그 원소를 꺼내고 뒤의 원소들을 한 칸씩 옮겨주어야해서 O(n)의 시간이 걸리기 때문이다. 그렇지만 deque의 popleft는 가장 앞의 값을 꺼내는 연산의 시간복잡도가 O(1)이기 때문에 가장 앞의 값을 꺼내야할 때는 deque를 사용하는 것이 효율적이다.