백준 문제 중 10866번, 덱, ‘덱’
백준 문제 중 10866번
https://www.acmicpc.net/problem/10866
문제
정수를 저장하는 덱(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보다 작거나 같다. 문제에 나와있지 않은 명령이 주어지는 경우는 없다.
출력
출력해야하는 명령이 주어질 때마다, 한 줄에 하나씩 출력한다.
풀이
- 내장 deque 라이브러리 활용
from collections import deque
from typing import Any
class Deque:
def __init__(self,capacity:int=10000)->None:
self.deq = deque(maxlen=capacity)
def push_front(self,x:int)->None:
self.deq.appendleft(x)
def push_back(self,x:int)->None:
self.deq.append(x)
def pop_front(self)->Any:
if len(self.deq)<=0: return -1
else: return self.deq.popleft()
def pop_back(self)->Any:
if len(self.deq)<=0: return -1
else: return self.deq.pop()
def size(self)->int:
return len(self.deq)
def empty(self)->None:
return 1 if self.deq.__len__()<=0 else 0
def front(self)->None:
if len(self.deq)<=0: return -1
else: return self.deq[0]
def back(self)->None:
if len(self.deq)<=0: return -1
else: return self.deq[-1]
n = int(input())
x = Deque()
ans = []
for i in range(n):
cmd = input().split()
if cmd[0] == 'push_front': x.push_front(int(cmd[1]))
elif cmd[0] == 'push_back': x.push_back(int(cmd[1]))
elif cmd[0] == 'pop_front': ans.append(x.pop_front())
elif cmd[0] == 'pop_back': ans.append(x.pop_back())
elif cmd[0] == 'size': ans.append(x.size())
elif cmd[0] == 'empty': ans.append(x.empty())
elif cmd[0] == 'front': ans.append(x.front())
elif cmd[0] == 'back': ans.append(x.back())
for an in ans: print(an)
2
1
2
0
2
1
-1
0
1
-1
0
3
- 이중 연결리스트 활용
(2) DoublyLinkedList 에서 코드를 가져왔다.
from typing import Any,Type
# 노드 클래스 선언
class Node:
def __init__(self,data:Any,next=None,prev=None)->None:
# 전방 탐색을 위해 prev필드 추가
self.data = data
self.next = next
self.prev = prev
# 이중연결리스트 클래스 선언
class DoublyLinkedList:
# 시작 head, 현재 cur, 갯수 no 선언
def __init__(self):
self.head = None
self.cur = None
self.no = 0
# dunder 함수로 len구현
def __len__(self):
return self.no
# 원하는 데이터를 찾는 함수
def search(self,data:Any)->int:
# data의 인덱스를 나타낼 변수
cnt = 0
# head 부터 시작해서 노드가 none이 될때까지 next
p = self.head
while p is not None:
# 스캔중 data 발견시 return cnt
if p.data == data:
self.cur = p
return cnt
p = p.next
cnt+=1
# 검색 실패시 return -1
return -1
# 머리에 노드추가 함수
def add_first(self,data:Any)->None:
self.head = Node(data,self.head)
self.no+=1
# head.next가 존재 할시 prev가 self.head를 가르키도록 할당
if self.head.next is not None:
self.head.next.prev = self.head
# 꼬리 노드추가 함수
def add_last(self,data:Any)->None:
# 리스트가 비었다면 머리추가와 동일
if self.head is None:
self.add_first(data)
else:
# p.next가 None 즉 마지막 노드까지 스캔
p = self.head
while p.next is not None:
p = p.next
# 마지막노드 p의 next에 data를 data로 prev를 p로 갖는 노드 추가
# cur, no 업데이트
p.next = self.cur = Node(data,None,p)
self.no+=1
# 머리노드 삭제 함수
def remove_first(self)->Any:
# 리스트가 비었다면 삭제 실패 False 반환
if self.head is None:
return -1
# head가 None이 아니라면 head를 삭제
# cur, no 업데이트 후 True 반환
else:
x = self.head.data
self.head = self.cur = self.head.next
self.head.prev = None
self.no-=1
return x
# 꼬리노드 삭제 함수
def remove_last(self)->bool:
# 리스트가 비었다면 false 반환
if self.head is None:
return -1
# p.next가 none 즉 마지막 노드까지 스캔
# 단. pre에 이전 p를 저장하며 진행
else:
p = self.head
pre = self.head
while p.next is not None:
pre = p
p = p.next
x = p.data
# 마지막 노드 p의 전 노드 pre의 next를 None으로 업데이트
pre.next = None
# p의 prev에 None 할당
p.prev = None
self.cur = pre
self.no-=1
return x
# 노드x를 삭제하는 함수
def remove(self,x:Node)->None:
# 리스트가 비었다면 false 반환
if self.head is None:
return False
else:
p = self.head
pre = self.head
# p의 next와 x가 일치할때 까지 진행
while p.next is not x:
pre = p
p = p.next
# 마지막 노드까지 없다면 false 반환
if p is None:
return False
# p의 next가 x이므로 p.next에 x의 next 대입
p.next = x.next
# p의 next가 None이 아니라면 prev에 pre 할당
if p.next is not None:
p.next.prev = pre
self.cur = p
self.no-=1
def remove_cur_node(self)->None:
self.remove(self.cur)
def print_cur_node(self)->None:
if self.cur is None: print('None')
else: print(self.cur.data)
def print(self)->None:
p=self.head
while p is not None:
print(p.data)
p=p.next
def print_reverse(self)->None:
p=self.head
while p.next is not None:
p=p.next
while p is not None:
print(p.data)
p=p.prev
def clear(self)->None:
while self.head is not None:
self.remove_first()
self.cur = None
self.no
class Deque:
def __init__(self):
self.deq = DoublyLinkedList()
def push_front(self,x:int)->None:
self.deq.add_first(x)
def push_back(self,x:int)->None:
self.deq.add_last(x)
def pop_front(self)->Any:
if len(self.deq)<=0: return -1
else:
return self.deq.remove_first()
def pop_back(self)->Any:
if len(self.deq)<=0: return -1
else:
return self.deq.remove_last()
def size(self)->int:
return len(self.deq)
def empty(self)->None:
return 1 if self.deq.__len__()<=0 else 0
def front(self)->Any:
if len(self.deq)<=0: return -1
else:
p = self.deq.head
return p.data
def back(self)->Any:
if len(self.deq)<=0: return -1
else:
p = self.deq.head
while p.next is not None:
p=p.next
return p.data
def print(self)->None:
self.deq.print()
x = Deque()
x.push_front(1)
x.push_front(2)
x.push_back(5)
x.push_back(4)
x.push_front(7)
x.push_front(8)
print(f'pop_back:{x.pop_back()}')
print(f'pop_front:{x.pop_front()}')
print()
print(
x.size(),
x.empty(),
x.front(),
x.back()
)
print()
x.print()
pop_back:4
pop_front:8
4 0 7 5
7
2
1
5
Leave a comment