[Baekjoon] 18258 - 큐 2 (Python)

문제

[BaekJoon] 18258 큐 2

풀이

파이썬에선 deque()를 이용해서 큐를 구현하면 되는데, deque()를 사용하지 않고 list를 사용해 풀면서 del을 사용해봤지만 시간초과가 났다. 아마도 pop()의 시간 복잡도 O(1) 반해 del의 시간 복잡도가 O(N)이라 초과되지 않았을까 싶다.

그래서 pop(0)을 썼는데..

import sys
n = int(sys.stdin.readline())

queue = []
for _ in range(n):
    operate = sys.stdin.readline().split()

    if operate[0] == 'push':
        queue.append(operate[1])
    elif operate[0] == 'pop':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue.pop(0))
    elif operate[0] == 'size':
        print(len(queue))
    elif operate[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else: 
            print(0)
    elif operate[0] == 'front':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])
    elif operate[0] == 'back':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[-1])

코드는 문제없이 잘 동작하지만 결과는 시간초과 ㅎ..

그래서 그냥 deque() 사용해서 작성했다. 정답!

import sys
from collections import deque

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

queue = deque()
for _ in range(n):
    operation = sys.stdin.readline().split()

    if operation[0] == 'push':
        queue.append(operation[1])
    elif operation[0] == 'pop':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue.popleft())
    elif operation[0] == 'size':
        print(len(queue))
    elif operation[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else: 
            print(0)
    elif operation[0] == 'front':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[0])
    elif operation[0] == 'back':
        if len(queue) == 0:
            print(-1)
        else:
            print(queue[-1])

---

deque()

from collections import deque
deque = deque()

deque.append(x)

x를 오른쪽 끝에 삽입

deque.appendleft(x)

x를 왼쪽 끝에 삽입

deque.pop()

오른쪽 끝 삭제하고 값 반환

deque.popleft()

왼쪽 끝 삭제하고 값 반환

deque.extend(arr)

주어진 배열을 순환하면서 오른쪽에 추가

deque.extendleft(arr)

주어진 배열을 순환하면서 왼쪽에 추가

deque.remove(x)

x를 찾아서 삭제

deque.rotate(num)

deque를 num 만큼 회전 (양수면 오른쪽, 음수면 왼쪽)