백준 18258 큐 2 파이썬 [개인적인 풀이 과정]

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

18258번: 큐 2

 

전에 풀었던 10828 스택 문제와 상당히 유사하다. https://www.acmicpc.net/problem/10828

 

push, pop, size, empty 까지는 동일하고, 

front와 back이 추가 되었는데 스택에서는 top과 비슷한 개념이 앞 뒤에 달려있다고 봐도 될 것 같다.

 

 

import sys
input = sys.stdin.readline
n = int(input())
queue = []

for i in range(1, n+1):
    c = input().split()

    if c[0] == 'push':
        queue.append(c[1])
    
    elif c[0] == 'pop':
        if len(queue) == 0:
            print('-1')
        else:
            print(queue[0])
            del queue[0]

    elif c[0] == 'size':
        print(len(queue))
    
    elif c[0] == 'empty':
        if len(queue) == 0:
            print('1')
        else:
            print('0')
    
    elif c[0] == 'front':
        if len(queue) == 0:
            print('-1')
        else:
            print(queue[0])
    
    elif c[0] == 'back':
        if len(queue) == 0:
            print('-1')
        else:
            print(queue[-1])

시간초과가 나버린다...

 

 

알고리즘 그룹 스터디 하시는 분이 리스트 대신 deque로 해보라 하셔서 바꿨더니 바로 문제가 풀렸다.

deque를 임포트하고 queue 적힌 부분을 [] 빈 리스트가 아닌  deque([])로 시간 내에 작동했다.

deque의 특징은 아래와 같다.

• 시작점의 값을 넣고 빼거나, 끝 점의 값을 넣고 빼는 데 최적화된 연산 속도를 제공한다.
• 즉, 대부분의 경우 덱(deque)이 리스트(list)보다 월등한 옵션이다.
• 큐의 앞과 뒤에서 삽입과 삭제가 가능하다. 스택처럼 또는 큐처럼 사용할 수 있다.

import sys
from collections import deque

n = int(sys.stdin.readline())
queue = deque([])

for i in range(1, n+1):
    c = sys.stdin.readline().split()

    if c[0] == 'push':
        queue.append(c[1])
        
    
    elif c[0] == 'pop':
        if len(queue) == 0:
            print('-1')
        else:
            print(queue[0])
            del queue[0]

    elif c[0] == 'size':
        print(len(queue))
    
    elif c[0] == 'empty':
        if len(queue) == 0:
            print('1')
        else:
            print('0')
    
    elif c[0] == 'front':
        if len(queue) == 0:
            print('-1')
        else:
            print(queue[0])
    
    elif c[0] == 'back':
        if len(queue) == 0:
            print('-1')
        else:
            print(queue[-1])

 

함수로 구현하는 방법으로도 다시 풀어볼 예정이다.