Python 알고리즘 인터뷰 - 문제 26. 원형 데크 디자인

641. Design Circular Deque - https://leetcode.com/problems/design-circular-deque/submissions/1158874826/

 

다음 인터페이스를 만족하는 deque를 디자인한다.

myCircularDeque = MyCircularDeque(3);
myCircularDeque.insertLast(1);  #return True
myCircularDeque.insertLast(2);  #return True
myCircularDeque.insertFront(3); #return True
myCircularDeque.insertFront(4); #return False, the queue is full.
myCircularDeque.getRear();      #return 2
myCircularDeque.isFull();       #return True
myCircularDeque.deleteLast();   #return True
myCircularDeque.insertFront(4); #return True
myCircularDeque.getFront();     #return 4

 

풀이

다음과 같이 양방향 연결 노드를 사용하여 데크를 구현한다.

초기화는 다음과 같이 head, tail이 서로를 가리키도록 하며, 최대 길이 k를 초기화하고, 현재 길이 len을 0으로 초기화한다.

def __init__(self, k):
	self.head, self.tail = BiListNode(None), BiListNode(None)
    self.head.right = self.tail
    self.tail.left = self.head
    self.len, self.k = 0, k

 

deque는 양방향에서 insert가 가능한 자료 구조이다. 먼저 insertFront, insertLast 모두 _insert 라는 내부 함수를 통해 구현하는데 다음과 같은 순서로 진행된다.

먼저 n = node.right으로 설정 후 node right는 new_node를 가리키고, new_node의 left는 node, light는 n을 가리킨다. 마지막으로 n의 left가 new_node를 가리킨다. 코드는 다음과 같다. 

def _insert(self, node, value):
    new_node = BiListNode(value)
    n = node.right
    node.right = new_node
    new_node.left, new_node.right = node, n
    n.left = new_node
    self.len = self.len + 1

 

insertFront, insertLast 함수의 구현은 각각 다음과 같다.

def insertFront(self, value):
    return self._insert(self.head, new_node, value)
    
def insertLast(self, value):
    return self._insert(self.tail.left, new_node, value)

 

_insert 함수가 node의 오른쪽을 기준으로 추가를 진행하므로 insertLast는 tail의 왼쪽을 파라미터로 호출하여 진행한다.

 

_del 함수는 node.right.right을 right로 연결하고 node.right.right를 left로 연결하여 node.right를 삭제하도록 한다.

 

구현은 다음과 같다.

def _del(self, node):
	if self.len <= 0:
    	return False
    
    self.len = self.len - 1
    n = node.right.right
    node.right = n
    n.left = node
    return True

 

deleteFront, deleteLast 함수의 구현은 다음과 같다.

def deleteFront(self):
	return _del(self.head)
    
def deleteLast(self):
	return _del(self.tail.left.left)

 

나머지 getFront, getRear, isEmpty, isFull 함수를 포함한 전체 구현은 다음과 같다.

 

class BiListNode:
    def __init__(self, value):
        self.val = value
        self.left = None
        self.right = None


class MyCircularDeque(object):
    def __init__(self, k):
        self.head, self.tail = BiListNode(None), BiListNode(None)
        self.len, self.k = 0, k
        self.head.right, self.tail.left = self.tail, self.head

    def _insert(self, node, value):
        if self.len == self.k:
            return False

        new_node = BiListNode(value)
        n = node.right
        node.right = new_node
        new_node.left, new_node.right = node, n
        n.left = new_node
        self.len = self.len + 1
        return True

    def _del(self, node):
        if self.len <= 0:
            return False

        n = node.right.right
        node.right = n
        n.left = node
        self.len = self.len - 1
        return True

    def insertFront(self, value):
        return self._insert(self.head, value)

    def insertLast(self, value):
        return self._insert(self.tail.left, value)

    def deleteFront(self):
        return self._del(self.head)

    def deleteLast(self):
        return self._del(self.tail.left.left)

    def getFront(self):
        return self.head.right.val if self.len else -1

    def getRear(self):
        return self.tail.left.val if self.len else -1

    def isEmpty(self):
        return self.len == 0

    def isFull(self):
        return self.len == self.k