데크 , 우선순위 큐

데크

• 더블 엔디드 큐(Double-Ended Queue)의 줄임말로, 글자 그대로 양쪽 끝을 모두 추출할 수 있는, 큐를 일반화한 형태의 추상 자료형(ADT)이다.
• 데크는 양쪽에서 삭제와 삽입을 모두 처리할 수 있으며, 스택과 큐의 특징을 모두 갖고 있다.

문제 1. 원형 데크 디자인

다음 연산을 제공하는 원형 데크를 디자인하라.

• MyCircularDeque(k): 데크 사이즈를 k로 지정하는 생성자다.
• insertFront(): 데크 처음에 아이템을 추가하고 성공할 경우 true 리턴
• insertLast():데크 마지막에 아이템을 추가하고 성공할 경우 true 리턴
• deleteFront():데크 처음에 아이템을 삭제하고 성공할 경우 true 리턴
• deleteLast():데크 마지막에 아이템을 삭제하고 성공할 경우 true 리턴
• getFront():데크 첫 번째 아이템을 가져온다.데크가 비어 있다면 -1을 리턴
• getRear():데크 마지막 아이템을 가져온다.데크가 비어 있다면 -1을 리턴
• isEmpty(): 데크가 비어 있는지 여부를 판별한다.
• isFull(): 데크가 가득 차 있는지 여부를 판별한다.

이중 연결 리스트를 이용한 데크 구현 풀이

class MyCircularDeque:
    def __init__(self,k):
        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, new):
        n = node.right
        node.right = new
        new.left, new.right = node , n
        n.left = new
            
    def _del(self,node):
        n = node.right.right
        node.right = n
        n.left = node
        
    def insertFront(self,value):
        if self.len == self.k:
            return False
        self.len += 1
        self._add(self.head, ListNode(value))
        return True
        
    def insertLast(self,value):
        if self.len == self.k:
            return False
        self.len +=1
        self._add(self.tail.left, ListNode(value))
            
    def deleteFront(self):
        if self.len == 0:
            return False
        self.len -= 1
        self._del(self.head)
        return True
        
    def deleteLast(self):
        if self.len == 0 :
            return False
        self.len -= 1
        self._del(self.tail.left.left)
        return True
        
    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
        

• 최대 길이 정보는 k 이고, head 와 taile 은 각각 왼쪽, 오른쪽 인덱스 역할이다.
• 현재 길이 정보를 담는 변수인 len에는 0을 담는다.
• 새로운 노드 삽입 시 최대 길이에 도달했을 때는 False를 리턴하고, 이외에는 _add() 메서드를 이용해 head 위치에 노드를 삽입한다.
• 뒤 쪽에 추가하는 insertLast() 도 같은 방법으로 진행하면 된다.
• 삭제의 경우에는 _add() 메서드를 _del() 메서드로 바꿔준다.

우선순위 큐

• 우선순위 큐는 큐 또는 스택과 같은 추상 자료형과 유사하지만 추가로 각 요소의 '우선순위'와 연관되어 있다.
• 우선순위 큐는 어떠한 특정 조건에 따라 우선순위가 가장 높은 요소가 추출되는 자료형이다. 예를 들면 최솟값을 추출하는 우선순위 큐에서는 [1,4,5,3,2] 를 넣으면 1,2,3,4,5 순으로 추출된다. ( 큐는 가장 먼저 삽입된 요소를 먼저 추출하고, 스택은 가장 나중에 삽입한 요소가 추출됨 )

문제 2. k개 정렬 리스트 병합

k개의 정렬된 리스트를 1개의 정렬된 리스트로 병합하라.

• ex ) [ 1->4->5 , 1->3->4 , 2->6 ] 이 입력된다면 1 -> 1 -> 2 -> 3 -> 4 -> 4 -> 5 -> 6 이 출력된다. ( 여기서 k는 3이다. )

우선순위 큐를 이용한 리스트 병합

def mergeKLists(self,lists):
    root = result = ListNode(None)
    heap = []
    
    # 각 연결 리스트의 루트를 힙에 저장
    for i in range(len(lists)):
        if lists[i]:
            heapq.heappush(heap, (lists[i].val, i , lists[i]))
    
    # 힙 추출 이후 다음 노드는 다시 저장
    while heap :
        node = heapq.heappop(head)
        idx = node[1]
        result.next = node[2]
        
        result = result.next
        if result.next:
            heapq.heappush(heap, (result.next.val, idx, result.next))
    
    return root.next

• 파이썬에서는 우선순위 큐 풀이에 거의 항상 heapq 율을 사용한다.
• heappush 함수를 이용해 힙에 넣으면, heappop()으로 값을 추출했을 때 가장 작은 노드의 연결 리스트부터 차례대로 나오게 된다.