[leetcode] design-circular-deque

문제: https://leetcode.com/problems/design-circular-deque/submissions/

참고도서: 파이썬 알고리즘 리뷰

1. 접근방법

자료구조를 구현하는 문제이기에 직관적으로 접근했다.

• deqeue는 python collections 모듈에 linked-list 로 구현되어있음
• head, tail node를 지정하고 이를 이용해서 데이터를 삽입, 삭제하도록 함

2. 풀이

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()

3. 후기

_add, _del의 과정을 머릿속으로 생각해봤다.

• _add: target node, New node 두가지를 받아서 Target Node의 오른쪽에 New node를 붙여준다.
  • insertFront 는 target에 head를 넣어서 구현 가능하다
• _del: target node를 삭제한다.
  • 책에서 제시한 내용은 target node를 받아서 오른쪽의 노드를 삭제한다.
  • 하지만 난 좀 더 직관적으로 생각하고 싶어서 target node를 삭제하는 쪽으로 선회하였다.
  • target.left 와 target.right를 이어주면 된다.
  • 구조 변경에 따라서 deleteFront, deleteLast가 변경되었다.

insertFront를 작성하면서 _add()의 존재를 확인했다.

• 기존에는 add를 구현하고 나서 insertFront를 구현하는 순차적인 방식을 고수했었다.
• 하지만 python 에서 pass 구문을 통해서 구현은 나중에 미루는 식으로 코드를 구현한 적이 있었다
• 기능에 대한 아이디어가 명확할 경우 순차적인 방식을 고수할 필요는 없다고 생각이 들었다.