[백준] 10866번 덱 [Python]

덱$($deque, double-ended queue$)$은 파이썬의 collections 모듈에 포함된 자료구조로, 양쪽 끝에서 원소를 추가하거나 제거할 수 있는 큐$($Queue$)$의 확장된 형태입니다. 덱은 리스트$($list$)$와 유사하지만, 리스트보다 효율적인 양방향 연산을 지원합니다. 이러한 특징 때문에 덱는 다양한 상황에서 유용하게 사용될 수 있습니다.

from collections import deque

# 데크 생성
deque_list = deque

# 데크의 오른쪽에 원소 추가
deque_list.append$1$
deque_list.append$2$
deque_list.append$3$

# 데크의 왼쪽에 원소 추가
deque_list.appendleft$0$

# 데크 출력
print$deque_list$  # 출력: deque$[0, 1, 2, 3]$

# 데크의 오른쪽에서 원소 제거
deque_list.pop

# 데크의 왼쪽에서 원소 제거
deque_list.popleft

# 데크 출력
print$deque_list$  # 출력: deque$[1, 2]$

 

1. 큐$($Queue$)$ 구현:
   덱는 양쪽에서 삽입과 삭제가 가능한 큐로 사용될 수 있습니다. 큐는 선입선출$($FIFO$)$ 구조를 가지며, 데크를 이용하면 원소를 앞과 뒤에서 빠르게 삽입/삭제할 수 있어서 큐를 효율적으로 구현할 수 있습니다.
   
   
2. 스택$($Stack$)$ 구현:
   덱는 양쪽에서 삽입과 삭제가 가능하므로 스택$($Stack$)$을 구현하는 데에도 사용될 수 있습니다. 스택은 후입선출$($LIFO$)$ 구조를 가지며, 데크의 양쪽에서 pop과 append 메서드를 사용하여 스택을 구현할 수 있습니다.
   
   
3. 원형 버퍼$($Circular Buffer$)$ 구현:
   데크는 최대 길이를 지정할 수 있기 때문에, 원형 버퍼를 구현하는데에도 유용합니다. 원형 버퍼는 고정된 크기를 가진 버퍼로, 새로운 원소가 추가될 때 최근 원소를 덮어쓰는 방식으로 동작합니다. 데크를 이용하여 원형 버퍼를 구현하면 메모리를 효율적으로 관리할 수 있습니다.
   
   
4. 슬라이딩 윈도우$($Sliding Window$)$ 문제:
   슬라이딩 윈도우 문제는 주어진 배열에서 특정 크기의 윈도우를 이동시키면서 원하는 연산을 수행하는 문제입니다. 데크를 사용하면 슬라이딩 윈도우 문제를 효율적으로 해결할 수 있습니다.
   
   
5. 중복 원소 관리:
   데크는 중복된 원소를 허용하며, 원소들의 순서를 보존합니다. 따라서 중복 원소가 있는 데이터를 관리할 때 유용하게 사용될 수 있습니다.

 

문제

정수를 저장하는 덱$($Deque$)$를 구현한 다음, 입력으로 주어지는 명령을 처리하는 프로그램을 작성하시오.

명령은 총 여덟 가지이다.

• push_front X: 정수 X를 덱의 앞에 넣는다.
• push_back X: 정수 X를 덱의 뒤에 넣는다.
• pop_front: 덱의 가장 앞에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• pop_back: 덱의 가장 뒤에 있는 수를 빼고, 그 수를 출력한다. 만약, 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• size: 덱에 들어있는 정수의 개수를 출력한다.
• empty: 덱이 비어있으면 1을, 아니면 0을 출력한다.
• front: 덱의 가장 앞에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.
• back: 덱의 가장 뒤에 있는 정수를 출력한다. 만약 덱에 들어있는 정수가 없는 경우에는 -1을 출력한다.

입력

첫째 줄에 주어지는 명령의 수 N $($1 ≤ N ≤ 10,000$)$이 주어진다. 둘째 줄부터 N개의 줄에는 명령이 하나씩 주어진다. 주어지는 정수는 1보다 크거나 같고, 100,000보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.

출력

출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.

 

 

import sys
input = sys.stdin.readline

N = int(input())
l = [0] * N
for i in range(N):
    l[i] = list(map(str,input().split()))

class Deque:
    deque = []

    def push_front(self, n):
        self.n = n
        Deque.deque.insert(0, self.n)

    def push_back(self, n):
        self.n = n
        Deque.deque.append(self.n)

    def pop_front(self):
        if Deque.deque == []:
            print(-1)
        else :
            print(Deque.deque.pop(0))

    def pop_back(self):
        if Deque.deque == []:
            print(-1)
        else :
            print(Deque.deque.pop())
    
    def size(self):
        print(len(Deque.deque))

    def empty(self):
        if len(Deque.deque) != 0:
            print(0)
        else:
            print(1)

    def front(self):
        if len(Deque.deque) == 0:
            print(-1)
        else:
            print(Deque.deque[0])

    def back(self):
        if len(Deque.deque) == 0:
            print(-1)
        else:
            print(Deque.deque[-1])

for i in range(N):
    if len(l[i]) == 2:
        getattr(Deque(), l[i][0])(int(l[i][1]))
    else:
        getattr(Deque(), l[i][0])()

 

 

예제 입력 1 

15
push_back 1
push_front 2
front
back
size
empty
pop_front
pop_back
pop_front
size
empty
pop_back
push_front 3
empty
front

예제 출력 1 

2
1
2
0
2
1
-1
0
1
-1
0
3

예제 입력 2 

22
front
back
pop_front
pop_back
push_front 1
front
pop_back
push_back 2
back
pop_front
push_front 10
push_front 333
front
back
pop_back
pop_back
push_back 20
push_back 1234
front
back
pop_back
pop_back

예제 출력 2 

-1
-1
-1
-1
1
1
2
2
333
10
10
333
20
1234
1234
20