26. Design Circular Deque

🎯 leetcode - 641. Design Circular Deque

🤔 나의 풀이

📌 문제

- 파이썬 알고리즘 인터뷰 26번 문제

📌 날짜

2020.02.01

📌 시도 횟수

2 try

💡 Code

class MyCircularDeque:
    def __init__(self, k: int):
        self.head, self.tail = ListNode(None), ListNode(None)
        self.max_len, self.len = k, 0
        self.head.right, self.tail.left = self.tail, self.head

    # _add : node의 오른쪽에 new를 삽입한다
    def _add(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new

    # _del : node의 오른쪽 노드를 삭제한다.
    def _del(self, node: ListNode):
        n = node.right.right
        node.right = n
        n.left = node

    def insertFront(self, value: int) -> bool:
        if self.len == self.max_len:
            return False
        self.len += 1
        # self.head의 "오른쪽"에 신규 노드 삽입
        self._add(self.head, ListNode(value))
        return True

    def insertLast(self, value: int) -> bool:
        if self.len == self.max_len:
            return False
        self.len += 1
        # self.tail.left의 "오른쪽"에 신규 노드 삽입
        self._add(self.tail.left, ListNode(value))
        return True

    def deleteFront(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        # self.head의 "오른쪽" 노드를 삭제
        self._del(self.head)
        return True

    def deleteLast(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        # self.tail.left.left의 "오른쪽" 노드를 삭제
        self._del(self.tail.left.left)
        return True

    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.max_len
        
    # ------------ 디버깅용 ----ㅋ --------
    def printDeque(self):
        node = ListNode(0)
        node.right = self.head.right
        for _ in range(self.len):
            print(node.right.val, end="->")
            node = node.right
        print()

💡 문제 해결 방법

✔ 위의 문제는 _add(node, new)와 _del(node) 만 이해하면 된다.
>> insertFront, insertLast는 둘 다 _add(node, new) 함수를 통해 처리하고,
>> deleteFront, deleteLast는 둘 다 _del(node) 함수를 통해 처리한다.

✔ 처음에는 의문이 들었다. insertFront는 head의 "오른쪽"에 삽입하는 것이고,
insertLast는 tail의 "왼쪽"에 삽입하는 것인데 어떻게 _add를 통해 둘 다 처리할 수 있는걸까?

✔ 위의 문제는 조금만 생각하면 해결할 수 있었다. 바로 insertLast에서
"tail의 왼쪽" == "tail.left의 오른쪽"으로 바꾸어 생각하면 됐기 때문이다!

✔ 따라서 _add(node, new)의 경우에는 node의 "오른쪽"에 new를 삽입하되,
>> insertFront에서는 node가 self.head이고,
>> insertLast에서는 node가 self.tail.left이다.

✔ 비슷한 방법으로 _del(node) 또한 node의 "오른쪽"을 제거하되,
>> deleteFront에서는 node가 self.head이고,
>> deleteLast에서는 node가 self.tail.left.left이다.

🥰 추가 설명

• insertFirst, insertLast 만 따로 그림으로 그려 이해해보았다.
  
  

💡 새롭게 알게 된 점

- deque를 이중연결리스트로 구현할 때...
head, tail의 경우에는 실제 값을 가지지 않고 원형 deque의 head, tail임을 
표시하는 역할만 해주는 것을 알게 되었다.