오답 코드

import sys
input = sys.stdin.readline

N=int(input())
queue = []

for _ in range(N):
    commands = list(input().split())
    if commands[0]=='push':
        queue.append(commands[1])
    elif commands[0]=='pop':
        if queue:
            print(queue.pop(0))
        else:
            print(-1)
    elif commands[0]=='size':
        print(len(queue))
    elif commands[0]=='empty':
        if(len(queue)==0):
            print(1)
        else:
            print(0)
    elif commands[0]=='front':
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif commands[0]=='back':
        if queue:
            print(queue[len(queue)-1])
        else:
            print(-1)

오답인 이유

제출하니 시간초과가 발생했다.

여기서 시간복잡도를 더 단축해야 정답이 된다는 뜻이다.
어디를 줄여야 시간복잡도가 줄어들까 싶어서 보니
.pop(0)과 .append(commands[1]) 두 메서드 부분 중 하나라고 생각했다.

pop(0)의 시간복잡도

결론부터 얘기하면 pop(0)의 시간복잡도는 O(N)이다.
리스트 연산인 pop(0)은 인덱스0을 반환하고 0을 제외한 나머지 리스트를
인덱스를 한칸씩 땡기며 저장하기 때문에 결국 마지막 원소까지 인덱스에 따라 옮기는 작업이 필요하다.
반면 pop()의 시간복잡도는 O(1)이다.
리스트의 원소들을 한칸씩 땡기는게 아닌 마지막 원소의 연결만 끊으면 되기 때문이다.

append()의 시간복잡도

append()의 시간복잡도는 O(1)이다.
왜냐하면 파이썬에서 인덱스 마지막에 데이터 노드를 하나만 연결하면 되기 때문이다.

정답 코드

import sys
input = sys.stdin.readline


N=int(input())
queue = []
point = 0

for _ in range(N):
    commands = list(input().split())
    if commands[0]=='push':
        queue.append(commands[1])
    elif commands[0]=='pop':
        if len(queue)>point:
            print(queue[point])
            point+=1
        else:
            print(-1)
    elif commands[0]=='size':
        print(len(queue)-point)
    elif commands[0]=='empty':
        if(point==len(queue)):
            print(1)
            queue = []
            point = 0
        else:
            print(0)
    elif commands[0]=='front':
        if len(queue)>point:
            print(queue[point])
        else:
            print(-1)
    elif commands[0]=='back':
        if len(queue)>point:
            print(queue[-1])
        else:
            print(-1)

정답 풀이 아이디어

point변수를 사용해 리스트에서 삭제하는 대신
point로 큐의 맨 앞 원소를 인덱스로 지정한다.
리스트의 맨 앞 인덱스를 가리키는 point변수를 설정해서
pop으로 삭제된 원소값과 아닌 원소값을 구분해준다.