[CodingTest] 백준 #18258 큐 2

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

18258번: 큐 2

 

리스트로 해서 풀었더니 시간 초과가 나왔다.

pop(0) 을 하면 내부에서 앞으로 당기는 것 때문에 O(n)이 되어 그런 것 같았다.

그래서 deque를 사용했더니 통과했다.

 

 

시도 1 - [ ] 사용, 시간초과

n=int(input())
queue=[]
for i in range(n):
    line = input()
    if "push" in line:
        a,num=line.split()
        queue.append(num)
    elif line=="pop":
        if queue:
            print(queue.pop(0))
        else:
            print(-1)
    elif line=="size":
        print(len(queue))
    elif line=="front":
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif line=="back":
        if queue:
            print(queue[-1])
        else:
            print(-1) 
    elif line=="empty":
        if queue:
            print(0)
        else:
            print(1)

 

 

시도 2 - deque 사용 , 통과

import sys
from collections import deque 
n=int(sys.stdin.readline())
queue=deque()
for i in range(n):
    line = sys.stdin.readline().strip()
    if "push" in line:
        a,num=line.split()
        queue.append(num)
    elif line=="pop":
        if queue:
            print(queue.popleft())
        else:
            print(-1)
    elif line=="size":
        print(len(queue))
    elif line=="front":
        if queue:
            print(queue[0])
        else:
            print(-1)
    elif line=="back":
        if queue:
            print(queue[-1])
        else:
            print(-1) 
    elif line=="empty":
        if queue:
            print(0)
        else:
            print(1)

 

예전에 C할 때 구현했던 대로 front와 rear를 사용해서 푼 풀이도 있었다.

하지만 deque가 넘나 편리한 것..