Computer Vision 대학원생 기록지

10845번: 큐 (acmicpc.net)

REVIEW

• 문제에서 요구하는 pop은 리스트에 사용되는 pop( ) 명령어와 다르다. pop( )은 리스트 가장 마지막 element를 추출하는 반면, 문제에서는 큐의 첫 번째 element를 추출할 것을 요구한다. 
• 문제를 리스트로 구현할 시에 가장 앞에 있는 element를 pop(0)으로 추출할 수 있지만, 시간 복잡도가 O(N)이 되어 효율적인 방법이라고 볼 수 없다. 
• 따라서 이번 문제를 구현하기 위해서는 리스트가 아닌 collections 라이브러리의 deque를 사용하였다. 
• deque에서 가장 앞에 있는 element를 추출하기 위해서는 popleft( ) 명령어를 사용하면 된다. 해당 과정의 시간 복잡도는 O(1)으로 리스트의 pop(0)보다 훨씬 더 효율적이다. 

from collections import deque
import sys

N = int(input())
# 큐 생성
queue = deque()

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

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

    elif cmd[0] == 'pop':
        # 가장 왼쪽에 있는 element 추출
        try:
            print(queue.popleft())
        # 큐에서 추출할 element가 없을 경우
        except:
            print(-1)

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

    elif cmd[0] == 'empty':
        if len(queue) == 0:
            print(1)
        else:
            print(0)
 
    elif cmd[0] == 'front':
        # 가장 왼쪽에 있는 element 조회
        try:
            print(queue[0])
        # 큐에서 조회할 element가 없을 경우
        except:
            print(-1)

    elif cmd[0] == 'back':
        # 가장 마지막에 있는 element 조회
        try:
            print(queue[-1])
        # 큐에서 조회할 element가 없을 경우
        except:
            print(-1)

다른 풀이를 보니 함수를 이용한 코드가 속도가 더 빠른 듯하다.