[백준] 10866 - 덱 - (python 파이썬)

문제링크: https://www.acmicpc.net/problem/10866

10866번: 덱

 

풀이과정 :

덱이란 앞과 뒤 모두 삽입 삭제가 가능한 양방향 큐이다.

큐와 마찬가지로 핵심은 모든 연산이 시간복잡도 O(1)에서 끝나야한다.(O(n)은 시간초과..)

처음에는 데큐 없이 push_front를 짜려고 하니 고생하다가... 데큐를 쓰기로 결정..!

나머지는 풀이랄것 없이 저번에 했던 큐 구현과 거의 동일하다. 

 

#덱을 사용하고, 시간복잡도가 O(1)이어야함
import sys
from collections import deque
lst = deque([])
front_index = 0
testcase = int(input())
for _ in range(testcase):
    command = list(sys.stdin.readline().split())
    if command[0] == "push_front":
        lst.appendleft(int(command[1]))
    elif command[0] == "push_back":
        lst.append(int(command[1]))
    elif command[0] == "pop_front":
        if len(lst): print(lst.popleft())
        else: print(-1)
    elif command[0] == "pop_back":
        if len(lst): print(lst.pop())
        else: print(-1)
    elif command[0] == "size":
        print(len(lst))
    elif command[0] == "empty":
        if len(lst) == 0: print(1)
        else: print(0)
    elif command[0] == "front":
        if len(lst): print(lst[0])
        else:print(-1)
    elif command[0] == "back":
        if len(lst): print(lst[-1])
        else:print(-1)

 

답(이미지)

 

후기 : 스택, 큐, 덱큐 모두 문제도 다뤄보았는데, 언뜻봐도 중요하고 자주활용될 것 같아,

몇번 더 풀어보는것이 좋을것 같다.