[파이썬 알고리즘 인터뷰][데크/우선순위큐] 원형 데크 디자인

이 글은 "파이썬 알고리즘 인터뷰 (박상길 지음)"을 읽고 주관적으로 요약한 글입니다. 

---

출처 : https://www.onlybook.co.kr/entry/algorithm-interview

 

문제 정의

원형 데크 설계

 

책에서 구현된 코드

class MyCircularDeque:
    def __init__(self, k: int):
        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 _add(self, node: ListNode, new: ListNode):
        n = node.right
        node.right = new
        new.left, new.right = node, n
        n.left = new
        
    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.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

    def deleteFront(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        self._del(self.head)
        return True

    def deleteLast(self) -> bool:
        if self.len == 0:
            return False
        self.len -= 1
        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.k

 

기억해야할 기법

• 연결 리스트로 만든 원형 큐 / 데크 구현해볼 것

 

내가 구현한 코드

class MyCircularDeque:

    def __init__(self, k: int):
        self.size = k
        self.arr = [-1] * k
        self.head = 0
        self.rear = k-1

    def insertFront(self, value: int) -> bool:
        if self.isFull():
            return False
        self.head = self.size - 1 if self.head == 0 else self.head - 1
        self.arr[self.head] = value
        return True

    def insertLast(self, value: int) -> bool:
        if self.isFull():
            return False
        self.rear = (self.rear + 1) % self.size
        self.arr[self.rear] = value
        return True

    def deleteFront(self) -> bool:
        if self.isEmpty():
            return False
        self.arr[self.head] = -1
        self.head = (self.head + 1) % self.size
        return True

    def deleteLast(self) -> bool:
        if self.isEmpty():
            return False
        self.arr[self.rear] = -1
        self.rear = self.size - 1 if self.rear == 0 else self.rear - 1
        return True

    def getFront(self) -> int:
        return self.arr[self.head]

    def getRear(self) -> int:
        return self.arr[self.rear]

    def isEmpty(self) -> bool:
        return (self.rear + 1) % self.size == self.head and self.arr[self.rear] == -1

    def isFull(self) -> bool:
        return (self.rear + 1) % self.size == self.head and self.arr[self.rear] != -1

• 내가 구현한 알고리즘

• 책에서 구현한 알고리즘

• 책에서는 일부러 이중 연결리스트로 구현하는 방법을 소개함
• 나는 저장하는 데이터가 int뿐이고 사이즈가 고정이라 list로 구현
• 연결 리스트로 구현해볼걸 그랬다