[백준 - python] 18258번: 큐 2

문제 링크

18258번: 큐 2

문제 풀이

import sys
from collections import deque

input = sys.stdin.readline

queue = deque([])

n = int(input())
for _ in range(n):
    order = input().split()
    match (order[0], len(queue) == 0):
        case ("push", _):
            queue.append(int(order[1]))
        case ("pop", True):
            print(-1)
        case ("pop", False):
            print(queue.popleft())
        case ("size", _):
            print(len(queue))
        case ("empty", True):
            print(1)
        case ("empty", False):
            print(0)
        case ("front", True):
            print(-1)
        case ("front", False):
            print(queue[0])
        case ("back", True):
            print(-1)
        case ("back", False):
            print(queue[-1])

18258 입출력 예시

 

*key point: 큐 자체의 FIFO(First In First Out) 방식을 구현하는 것은 크게 어렵지 않으나 python의 리스트 특성상 "pop"을 구현할 때 시간 초과 문제가 발생하기 쉽다. 리스트의 요소를 제거하는 경우 그 뒤의 모든 요소를 O(n)의 속도로 앞당겨야하기 때문이다. python에서는 collections 모듈의 deque를 사용하면 리스트를 스택이나 큐 원하는 방식으로 사용하여 O(1)의 속도로 매우 빠르게 만들 수 있다. 이러한 모듈 없이 구현하고자 할 경우에는 "pop"을 할 때 실제로 요소를 제거하는 것이 아니라 큐의 출구를 가리키는 index를 만들어 증가시키는 것으로 큐와 유사하게 만들 수 있다.