[백준] 18258번: 큐 2 - Python(파이썬)

import sys
from collections import deque

input = sys.stdin.readline

n = int(input())
q = deque()

for _ in range(n):
    a = input().strip().split()

    if a[0] == "push":
        q.append(a[1])

    elif a[0] == "pop":
        if q:
            print(q.popleft())
        else:
            print(-1)

    elif a[0] == "size":
        print(len(q))

    elif a[0] == "empty":
        if q:
            print('0')

        else:
            print('1')

    elif a[0] == "front":
        if q:
            print(q[0])
        else:
            print(-1)
    elif a[0] == "back":
        if q:
            print(q[-1])
        else:
            print(-1)

List로 queue 구현 시 시간초과 오류가 남. 

import sys
input = sys.stdin.readline

class Queue:
    def __init__(self):
        self.q = []

    def isEmpty(self):
        if len(self.q) == 0:
            return 1
        else:
            return 0

    def enqueue(self, elem):
        self.q.append(elem)

    def dequeue(self):
        if len(self.q) == 0:
            return -1
        else:
            return self.q.pop(0)

    def front(self):
        if self.isEmpty():
            return -1
        else:
            return self.q[0]

    def getSize(self):
        return len(self.q)

n = int(input())
q = Queue()

for i in range(n):
    a = input().strip().split()

    if a[0] == "push":
        q.enqueue(a[1])

    elif a[0] == "pop":
        print(q.dequeue())

    elif a[0] == "size":
        print(q.getSize())

    elif a[0] == "empty":
        print(q.isEmpty())

    elif a[0] == "front":
        print(q.front())

    elif a[0] == "back":
        if q.isEmpty():
            print(-1)
        else:
            print(q.q[-1])

 

list로 구현 시 pop의 시간 복잡도는 O(n)이다. 앞에 원소를 제거하고 나머지 원소를 전부 이동시켜줘야 하기 때문이다.

그래서 list로 구현하면 시간초과가 발생하게 된다. 

 

deque를 사용해서 구현해야 함. deque을 사용하면 popleft는 내부 포인터 연결만 조정해주면 되기 때문에 시간복잡도는 O(1)이다. 하지만 deque에서 원소 임의 접근 시에는 포인터를 따라 가야하므로 시간 복잡도는 O(n)이다.

 

문제의 의도는 단순 queue구현이 아니라 list와 deque의 시간 복잡도 차이를 이해하고 적절한 자료구조를 선택하는 지를 물어보는 것이었다.