[BOJ:18258] 큐2

문제

https://www.acmicpc.net/problem/18258

[

18258번: 큐 2

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

www.acmicpc.net

](https://www.acmicpc.net/problem/18258)

코드

import sys
from collections import deque

#sys.stdin = open("input.txt","rt")

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

q = deque()


for _ in range(n):
    cmd = sys.stdin.readline().rstrip().split()

    if cmd[0] == "push":
        q.append(cmd[1])
    elif cmd[0] == "pop":
        if len(q) == 0:
            print(-1)
        else:
            print(q.popleft())
    elif cmd[0] == "size":
        print(len(q))
    elif cmd[0] == "empty":
        if len(q) == 0:
            print(1)
        else:
            print(0)
    elif cmd[0] == "front":
        if len(q) == 0:
            print(-1)
        else:
            print(q[0])
    elif cmd[0] == "back":
        if len(q) == 0:
            print(-1)
        else:
            print(q[-1])

문제해결방법

• 파이썬의 덱을 이용해서 구현했다.
• 처음의 list로 큐를 구현했을 때는 시간초과가 났다. 큐의 pop 연산을 pop(0) 연산으로 수행했는데 파이썬에서 리스트는 가장 앞 요소를 제거하면 새로 리스트를 만들기 때문에 시간복잡도가 O(n)이 소요된다.
• 만약에 덱을 사용하지 않고 구현한다면 가장 앞을 가리키는 인덱스 변수를 선언해서 풀이해주면된다.
• 덱없이 구현한 큐2 풀이 (https://chancoding.tistory.com/35)