[백준] 18258번 큐 2

 

⛏ 문제 파악

• 큐(queue)를 직접 간단하게 구현해보는 문제
• 큰 어려움은 없지만 제한 시간이 짧다.

👉🏻  답안

import sys
from collections import deque

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

queue = deque([])
for _ in range(K):
  x = sys.stdin.readline().split()

  if x[0] == 'push':
    queue.append(x[1])

  elif x[0] == 'pop':
    if len(queue) != 0:
      print(queue.popleft())
    else:
      print(-1)

  elif x[0] == 'size':
    print(len(queue))

  elif x[0] == 'empty':
    if len(queue) == 0:
      print(1)
    else:
      print(0)

  elif x[0] == 'front':
    if len(queue) != 0:
      print(queue[0])
    else:
      print(-1)

  elif x[0] == 'back':
    if len(queue) != 0:
      print(queue[len(queue)-1])
    else:
      print(-1)

📑  간단한 설명

• 배열의 [0] 인덱스의 값을 제거하기위해, 일반적으로 사용하는 pop(0) 이나 del을 사용하면 시간초과가 난다.
• 왜냐하면 이 두 함수는 배열을 제거하고 모든 배열을 이동시켜야하기 때문에 시간 복잡도가 O(N)이기 때문이다.
• 그래서 collections 모듈의 deque(double-ended queue)를 사용했다.
• 큐는 선입선출 방식이지만, deque은 양방향에서 삽입과 삭제가 가능하기에, deque의 시간 복잡도는 O(1)이 된다.
• 즉 시간을 효율적으로 사용할 수 있다.