18258 Queue2(큐2) with Python3

2023.02.24

0. Background

Queue 1 problem in baekjoon has been done but queue 2 problem has to be O(1) in time complexity. I could not solve this on my own and would like to write down here what I've found and learnt to resolve it.

 

1. Issue

1-1. Queue 1 code

n = int(input())
queue = []
commands = [input() for _ in range(n)]

for command in commands:
    if "push" in command:
        queue.append(int(command.split(" ")[1]))
    elif "pop" in command:
        if queue:
            print(queue.pop(0))
        else:
            print(-1)
    elif "size" in command:
        print(len(queue))
    elif "empty" in command:
        if queue:
            print(0)
        else:
            print(1)
    elif "front" in command:
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif "back" in command:
        if queue:
            print(queue[-1])
        else:
            print(-1)

I've implemented queue using python and got it passed. However, queue 2 requires deeper understanding of queue.

 

1-2. First Cause of timeout: Pop(0)

When pop(0), which is list function, is commanded, elements of a list should be moved to the left of them. In that process, time complexity becomes O(n). 

 

1-3. Second Cause of timeout: Input()

Input() could cause timeout. When only one input line is requested and time limit is loose, it would be fine to use input(). However, in the case to get several lines of input and have tight time limit, you might want to use sys.stdin.readline. 

 

2. Solution

The most of solutions suggested online are to use deque and sys.stdin.readline instead of list and input(). 

from collections import deque
import sys

input = sys.stdin.readline

n = int(input())
q = deque([])
commands = [input() for _ in range(n)]

for command in commands:
    if "push" in command:
            q.append(int(command.split(" ")[1]))
    elif "pop" in command:
        if len(q):
            print(q.popleft())
        else:
            print(-1)
    elif "size" in command:
        print(len(q))
    elif "empty" in command:
        if len(q):
            print(0)
        else:
            print(1)
    elif "front" in command:
        if len(q):
            print(q[0])
        else:
            print(-1)
    elif "back" in command:
        if len(q):
            print(q[-1])
        else:
            print(-1)