백준 18258 문제풀이 [python]

포스팅에 앞서 내용이 틀릴 수 있습니다.
해당 부분 지적 감사히 받습니다.

문제를 보자.

그냥 간단한 큐 구현 문제이다.

 

하지만 알아둬야 할 점이 있다.

 

시간초과 오류를 받을 수 있는데, 해당 문제를 해결하기 위해 deque를 사용해야 한다.

 

list는 pop을 통해 요소를 삭제하면, 나머지 요소들을 한 칸씩 당기게 된다.

 

여기서 O(n)의 시간복잡도가 발생한다.

 

하지만 deque의 경우 양방향 삽입삭제가 가능하다.

 

따라서 popleft()를 수행하여도 모든 요소를 1씩 당겨줄 필요가 없기 때문에 시간복잡도는 O(1)을 갖게 된다.

 

코드

import sys as s

from collections import deque

n = int(s.stdin.readline())

queue = deque()

def push(a):

    queue.append(a)

def pop():

    if len(queue):

        print(queue.popleft())

    else:

        print(-1)

       

def size():

    print(len(queue))

def empty():

    if len(queue):

        print(0)

    else:

        print(1)

def front():

    if len(queue):

        print(queue[0])

    else:

        print(-1)

def back():

    if len(queue):

        print(queue[-1])

    else:

        print(-1)

for _ in range(n):

    sen = s.stdin.readline().split()

    if sen[0] == 'push':

        push(int(sen[1]))

    elif sen[0] == 'pop':

        pop()

    elif sen[0] == 'size':

        size()

    elif sen[0] == 'empty':

        empty()

    elif sen[0] == 'front':

        front()

    elif sen[0] == 'back':

        back()

배운 점

1. list는 맨 끝단, deque는 양 끝단에서 삽입삭제가 가능하다.

2. list와 deque의 pop()은 시간복잡도가 O(1)이지만, popleft(), pop(0)은 각 O(1), O(n)의 시간복잡도가 걸린다.