[3부 선형 자료구조] 10장 데크, 우선순위 큐

📌 26) 원형 데크 디자인 ( 리트코드 641. Design Circular Deque )

✔ 풀이

class MyCircularDeque(object):

    def __init__(self, k):
        self.maxlen, self.len = k, 0
        self.head = ListNode(None)
        self.tail = ListNode(None)
        self.head.right, self.tail.left = self.tail, self.head
        
    def _add(self, node, new):  #(추가할 노드의 위치 보다 하나 앞의 위치에 있는 노드, 추가할 노드)
        n = node.right  #node의 다음 node를 n으로 지정
        node.right = new
        n.left = new
        new.left, new.right = node, n
    
    def _del(self, node): #(삭제할 노드의 위치 보다 하나 앞의 위치에 있는 노드)
        n = node.right.right  #node의 다음 다음 위치에 있는 node를 n으로 지정
        node.right = n
        n.left = node
        
    def insertFront(self, value):
        if self.len == self.maxlen:
            return False
        self.len += 1
        self._add(self.head, ListNode(value))
        return True
        
    def insertLast(self, value):
        if self.len == self.maxlen:
            return False
        self.len += 1
        self._add(self.tail.left, ListNode(value))
        return True
        

    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 -1 if self.len == 0 else self.head.right.val
        

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

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

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

📌 27) k개 정렬 리스트 병합 ( 리트코드 23. Merge k Sorted Lists )

✔ 풀이

# Definition for singly-linked list.
# class ListNode(object):
#     def __init__(self, val=0, next=None):
#         self.val = val
#         self.next = next

import heapq
class Solution(object):
    def mergeKLists(self, lists):
        root = result = ListNode(None)
        
        #우선순위 큐 사용 / (값, 인덱스(몇 번째 리스트인지), 연결리스트) / 인덱스(몇 번째 리스트인지)
        #중복을 막기 위해 인덱스 사용 => 중복이면 error 나기 때문에
        Q = []
        for i, list in enumerate(lists):
            if list:
                heapq.heappush(Q, (list.val, i, list))
        
        while Q:
            node = heapq.heappop(Q)
            idx = node[1]
            result.next = node[2]
            
            result = result.next #result이동
            if result.next:
                heapq.heappush(Q, (result.next.val, idx, result.next))
        
        return root.next