정수를 저장하는 덱(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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
예제 입력 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
나의 풀이
dequeue 라이브러리를 쓰지 않고 구현하는 것을 목표로 했다.
처음엔 기존에 작성한 Queue 클래스를 상속할까도 생각했지만 Singly linked list로 구현했기 때문에 불가능함을 깨달았다.
구현하다보니 왜 Doubly linked list를 써야 하는 지도 깨달을 수 있었다.
기존의 Singly linked list는 rear 노드가 이전 노드 정보를 저장하지 않기 때문에 push_back()을 처리 불가
따라서 Doubly linked list를 도입하여 rear 노드가 이전 노드 정보도 저장할 수 있도록 했다.
push 과정에서 새로 추가되는 temp 노드와 기존 노드와의 양 방향(next, prev)연결을 구성하는 것이 중요하다.
"""
Doubly linked list로 dequeue 구현.
"""
import sys
class Node():
def __init__(self, data):
# doubly linked list로 구현.
self.data = data
self.next = None
self.prev = None
class Dequeue():
def __init__(self):
self.f = None
self.r = None
self.num = 0
def push_front(self, x : int):
temp = Node(x)
if self.num == 0:
self.f = self.r = temp
else:
# self.f.prev는 계속 None으로 남음.
temp.next = self.f
self.f.prev = temp
self.f = temp
self.num += 1
def push_back(self, x : int):
temp = Node(x)
if self.num == 0:
self.f = self.r = temp
else:
# self.r.next는 계속 None으로 남음.
temp.prev = self.r
self.r.next = temp
self.r = temp
self.num += 1
def pop_front(self):
if self.num == 0:
print(-1)
return
print(self.f.data)
temp = self.f
self.f = temp.next
self.num -= 1
def pop_back(self):
if self.num == 0:
print(-1)
return
print(self.r.data)
temp = self.r
self.r = temp.prev
self.num -= 1
# size 함수
def size(self):
print(self.num)
# empty 함수
def empty(self):
print(1 if self.num == 0 else 0)
# front 함수
def front(self):
if self.num == 0:
print(-1)
return
print(self.f.data)
# back 함수
def back(self):
if self.num == 0:
print(-1)
return
print(self.r.data)
dequeue = Dequeue()
# 명령어 미리 저장
case = {
"pop_front" : lambda dequeue : dequeue.pop_front(),
"pop_back" : lambda dequeue : dequeue.pop_back(),
"size" : lambda dequeue : dequeue.size(),
"empty" : lambda dequeue : dequeue.empty(),
"front" : lambda dequeue : dequeue.front(),
"back" : lambda dequeue : dequeue.back(),
}
n = int(input())
for _ in range(n):
# 명령 수가 많아서 sys로 받음
command = sys.stdin.readline().rstrip().split()
if command[0] == "push_front":
dequeue.push_front(int(command[1]))
elif command[0] == "push_back":
dequeue.push_back(int(command[1]))
else:
case[command[0]](dequeue)
다른 사람 풀이
deque를 사용해서 풀었다. 실제 문제를 풀 때는 당연히 deque를 사용하는 것이 더 좋다.
from collections import deque
import sys
d = deque()
n = int(input())
for i in range(n):
command = sys.stdin.readline().split()
if command[0] == "push_front":
d.appendleft(command[1])
elif command[0] == "push_back":
d.append(command[1])
elif command[0] == "pop_front":
if d:
print(d[0])
d.popleft()
else:
print("-1")
elif command[0] == "pop_back":
if d:
print(d[len(d) - 1])
d.pop()
else:
print("-1")
elif command[0] == "size":
print(len(d))
elif command[0] == "empty":
if d:
print("0")
else:
print("1")
elif command[0] == "front":
if d:
print(d[0])
else:
print("-1")
elif command[0] == "back":
if d:
print(d[len(d) - 1])
else:
print("-1")
