백준 18258 파이썬 풀이 (큐 2, deque)

이전에 비슷한 문제를 풀어본 적이 있다.

저번에는 list를 활용해서 스택을 구현했었다.

이번에도 마친가지로 list를 활용해서 큐를 구현했다. 그러나 문제는 시간초과가 났다. 

찾아보니 list로 자료구조를 사용하는 것은 성능측면에서 비효율적이라고 한다.

그 이유는 list는 무작위 접근에 최적화된 구조이기 때문에 pop(0)이나 insert(0,x) 같은 경우는 상당히 불리한 연산이다. 이 두 연산의 시간 복잡도가 n이기 때문에 담고 있는 데이터가 많으면 많을수록 느려지게 된다.

따라서 list가 아닌 다른 형태로 자료구조를 만드는게 좋다고 한다.

 

그래서 deque를 사용해서 큐를 사용해 보았다.

from collections import deque
q = deque()
q.append(1) # q = [1]
q.append(3) # q = [3]
q.appendleft(2) # q = [2,1,3]

q.pop() # 3
q.popleft() # 2

len(q) # python3에서 가능하다고 함

재밌는 점은 appendleft, popleft같은 함수를 사용하여 원하는 방향에서 데이터를 뽑을 수 있다는 것이다.

사이즈 같은 경우는 내장함수 없이 len(q)를 사용하면 된다.

따라서 deque모듈을 사용하여 코딩을 진행했다.

import sys
from collections import deque
n = int(sys.stdin.readline())
q = deque()
for i in range(n):
    tmp = sys.stdin.readline()
    if "push" in tmp:
        q.append(tmp.split()[1])
    elif "pop" in tmp:
        if len(q) == 0:
            print(-1)
        else:
            print(q.popleft())
    elif "size" in tmp:
        print(len(q))
    elif "empty" in tmp:
        if len(q) == 0:
            print(1)
        else:
            print(0)
    elif "front" in tmp:
        if len(q) == 0:
            print(-1)
        else:
            print(q[0])
    else: # back
        if len(q) == 0:
            print(-1)
        else:
            print(q[-1])
    

코딩은 그냥 무식하게 진행했다. 별게 없다.

 

결론은 큐같은 자료구조를 구현할때 효율적으로 만들고 싶다면 list가 아닌 deque를 활용하면 좋다.