[백준 10866] 덱

10866번: 덱

알고리즘 : 덱

난이도 : 실버Ⅳ

 

1. 문제요약

• 문제이름 그대로 덱을 구현하는 문제이다.
• 명령어는 총 여덟가지인데, push_front X, push_back X, pop_front, pop_back, size, empty, front, back이다.
• 시간제한 0.5초이고 입력의 수 N은 1부터 10,000까지 이므로 $O(n^2)$이 되지 않게 구현한다.

2. 구현과정

• 입력이 많으므로 sys 모듈을 import하여 입력처리를 빠르게 한다.
• 자료구조 덱을 활용해야 시간복잡도를 맞출 수 있으므로 collections 모듈에서 deque를 import한다.
• 숫자를 push하는 명령어는 중간에 공백이 있으므로 나머지 명령어를 우선적으로 조건문으로 판단하고, 해당하지 않는 경우에는 input을 split하여 입력된 숫자값을 받는 식으로 구현한다.

3. 파이썬 코드

import sys
input = lambda: sys.stdin.readline().rstrip()
from collections import deque
deq = deque()

N = int(input())
for _ in range(N):
    order = input()
    if order == 'pop_front':
        print(deq.popleft() if deq else -1)
    elif order == 'pop_back':
        print(deq.pop() if deq else -1)
    elif order == 'size':
        print(len(deq))
    elif order == 'empty':
        print(1 if not deq else 0)
    elif order == 'front':
        print(deq[0] if deq else -1)
    elif order == 'back':
        print(deq[-1] if deq else -1)
    else: # push_front X or push_back X
        order,num = order.split()
        if order == 'push_front':
            deq.appendleft(num)
        else: # push_back
            deq.append(num)