[큐] 백준18258번 큐 2 with Python3

https://www.acmicpc.net/problem/18258

18258번: 큐 2

 

문제

 

내 풀이

import sys
n = int(sys.stdin.readline())

Q = []

for i in range(n):
    cmd = []
    cmd = list(sys.stdin.readline().split())
    if len(cmd) > 1:
        order = cmd[0]
        num = cmd[1]
    else:
        order = cmd[0]

    if order == 'push':
        Q.append(num)
    elif order == 'pop':
        if len(Q) > 0:
            print(Q[0])
            del Q[0]
        else:
            print('-1')
    elif order == 'size':
        print(len(Q))
    elif order == 'empty':
        if len(Q) > 0:
            print('0')
        else:
            print('1')
    elif order == 'back':
        if len(Q) > 0:
            print(Q[-1])
        else:
            print('-1')
    elif order == 'front':
        if len(Q) > 0:
            print(Q[0])
        else:
            print('-1')

해설

시간 복잡도를 해결 할 수가 없었다.

결국 시간초과

다른 사람의 풀이를 봐보자.

 

정답 풀이

import sys
from collections import deque
n = int(sys.stdin.readline())
q = deque([])
for i in range(n):
    s = sys.stdin.readline().split()
    if s[0] == 'push':
        q.append(s[1])
    elif s[0] == 'pop':
        if not q:
            print(-1)
        else:
            print(q.popleft())
    elif s[0] == 'size':
        print(len(q))
    elif s[0] == 'empty':
        if not q:
            print(1)
        else:
            print(0)
    elif s[0] == 'front':
        if not q:
            print(-1)
        else:
            print(q[0])
    elif s[0] == 'back':
        if not q:
            print(-1)
        else:
            print(q[-1])

출처:https://pacific-ocean.tistory.com/232

 

해석

pop를 할때 del함수를 써주게 되면 나머지 요소들이 앞으로 땡겨지는데 시간이 걸리므로

deque로 구현하여 popleft()함수를 써준다.

 

와우 deque! 시간 복잡도의 해결사!

pop, append를 양 끝의 엘리먼드에만 할 경우 앞도적으로 빠르다!.

 

https://chaewonkong.github.io/posts/python-deque.html