[백준] 18258 - 큐 2 (python)

문제 링크

큐는 선입선출이다. 아마 식당 알바를 하면 종종 냉장고에 붙어 있는 FIFO를 보게 되는데, First in First out이라는 뜻으로 스택의 First in Last out과는 다르다.
말그대로 먼저 넣으면 먼저 빼라정도 이다.

우리는 큐를 bfs할 때 자주 보지만 운영체제나 네트워크 하면서도 본다.

운영체제에서는 스케줄링 할 때 보게 된다. 대충 그냥 큐를 사용하면 CPU를 많이 사용하지 않는 프로세스들이 CPU를 오랫동안 사용하는 프로세스가 끝내기를 기다리는 현상이 발생해서 별로 좋지 않기 때문에 큐를 활용한 다양한 기법을 사용한다.

네트워크에서는 패킷교환 보게 된다. 패킷교환할 때 큐에다가 패킷을 넣고 대기시킨다. (이건 나도 기억이 잘 안난다.)

아무래도 스택이 익숙한 나에게 큐 특성상 pop이 구현하는데 시간이 걸렸다.

def pop():
    global l
    ans = 0
    if len(l) == 0:
        ans = -1
    elif len(l) == 1:
        ans = l[0]
        l = []
    else:
        ans = l[0]
        l = l[1:]
    return ans

처음 코드
그랬다가 뜨거운 시간초과를 맛보았다. 이유를 보건데 리스트에 두 개 이상의 요소가 있는 경우, 시간 복잡도는 O(n)이 된다고 한다. 이는 리스트를 슬라이싱하면 첫 번째 요소를 제외한 모든 요소로 새로운 리스트를 만들어야 하기 때문이다. 그래서 가장 하기 싫었던 deque를 활용하기로 하였다.(뭔가 이런 문제는 괜히 import해서 자료구조를 사용하면 존심이 상한다.)
덱이 비어있지 않은 경우, popleft의 시간 복잡도는 O(1)라고 한다. 좀전의 O(n)과는 유의미한 차이가 난다.

import sys
from collections import deque

input = sys.stdin.readline()

def push(x):
    l.append(x)

def size():
    global l
    return len(l)

def pop():
    global l
    ans = 0
    if len(l) == 0:
        return -1
    else:
        return l.popleft()

def empty():
    global l
    if len(l) == 0:
        return 1
    else:
        return 0

def front():
    global l
    if len(l)== 0:
        return -1
    else:
        return l[0]

def back():
    if len(l) == 0:
        return -1
    else:
        return l[-1]


n = int(input)
l = deque()
for i in range(n):
    input = sys.stdin.readline()
    tmp = input
    inputSplit = tmp.split()
    inp = inputSplit[0]

    if inp == 'push':
        push(inputSplit[1])
    elif inp == "pop":
        print(pop())
    elif inp == "size":
        print(size())
    elif inp == "empty":
        print(empty())
    elif inp == "front":
        print(front())
    elif inp == "back":
        print(back())

최종 코드

처음 deque 선언하는 부분과 pop부분만 맞게 바꾸었더니 잘 통과했다.