문제: https://leetcode.com/problems/design-circular-deque/submissions/
참고도서: 파이썬 알고리즘 리뷰
자료구조를 구현하는 문제이기에 직관적으로 접근했다.
class MyCircularDeque:
def __init__(self, k: int):
# head는 항상 가장 앞 노드 (None), tail은 항상 가장 뒤 노드 (None)
self.head, self.tail = ListNode(None), ListNode(None)
self.k, self.len = k, 0
self.head.right, self.tail.left = self.tail, self.head
def insertFront(self, value: int) -> bool:
if self.len == self.k:
return False
self.len += 1
self._add(self.head, ListNode(value))
return True
def insertLast(self, value: int) -> bool:
if self.len == self.k:
return False
self.len += 1
self._add(self.tail.left, ListNode(value))
return True
# add new node into target node's right
def _add(self, node: ListNode, new: ListNode):
n = node.right
node.right = new
new.left, new.right = node, n
n.left = new
# node n
# /\
# new
def deleteFront(self) -> bool:
if self.len == 0:
return False
self.len -= 1
self._del(self.head.right)
return True
def deleteLast(self) -> bool:
if self.len == 0:
return False
self.len -= 1
self._del(self.tail.left)
return True
# delete target node
def _del(self, node: ListNode):
left, right = node.left, node.right
left.right, right.left = right, left
def getFront(self) -> int:
return self.head.right.val if self.len else -1
def getRear(self) -> int:
return self.tail.left.val if self.len else -1
def isEmpty(self) -> bool:
return self.len == 0
def isFull(self) -> bool:
return self.len == self.k
# Your MyCircularDeque object will be instantiated and called as such:
# obj = MyCircularDeque(k)
# param_1 = obj.insertFront(value)
# param_2 = obj.insertLast(value)
# param_3 = obj.deleteFront()
# param_4 = obj.deleteLast()
# param_5 = obj.getFront()
# param_6 = obj.getRear()
# param_7 = obj.isEmpty()
# param_8 = obj.isFull()
_add, _del의 과정을 머릿속으로 생각해봤다.
insertFront를 작성하면서 _add()의 존재를 확인했다.