16강: 우선순위 큐(Priority Queues)

유태형·2022년 3월 11일

알고리즘 파이썬 프로그래머스

알고리즘 - Python

목록 보기

12/16

16강 요약

우선순위 큐는 일반적인 큐가 처리하는 순서인 FIFO와 다르게 우선순위에 따라 처리하는 데이터의 순서가 다릅니다.

내용

어떻게 우선순위 유지?

각각 다른 우선순위가 저장된 데이터들중 어느것을 먼저 실행하는지는 두단계에 선택적으로 선정될 수 있습니다.

enqueue : 데이터가 저장될 때 우선순위에 맞게 저장
dequeue : 큐에서 뺄때 가장 높은 우선순위 출력

우선순위 큐의 구현

일반적인 큐와 마찬가지로 배열을 이용한 큐와, 연결리스트를 이용한 큐로 구현 가능합니다.

우선순위 큐의 삽입, 출력

	def enqueue(self, x): #삽입(정렬)
        newNode = Node(x)
        curr = self.queue.head

        while curr.next.next and curr.next.data >= x:
            curr = curr.next
        self.queue.insertAfter(curr, newNode)

    def dequeue(self): #출력
        return self.queue.popAt(self.queue.getLength())

enqueue시 정렬하여 저장합니다. 즉 큐에는 우선순위에 따라 순서대로 정렬되어 있습니다. 일반적인 큐와 마찬가지로 가장 앞의 데이터를 출력하면 가장 높은 우선순위가 가장 먼저 출력됩니다.

문제

우선순위 큐

class Node:

    def __init__(self, item):
        self.data = item
        self.prev = None
        self.next = None


class DoublyLinkedList:

    def __init__(self):
        self.nodeCount = 0
        self.head = Node(None)
        self.tail = Node(None)
        self.head.prev = None
        self.head.next = self.tail
        self.tail.prev = self.head
        self.tail.next = None


    def __repr__(self):
        if self.nodeCount == 0:
            return 'LinkedList: empty'

        s = ''
        curr = self.head
        while curr.next.next:
            curr = curr.next
            s += repr(curr.data)
            if curr.next.next is not None:
                s += ' -> '
        return s


    def getLength(self):
        return self.nodeCount


    def traverse(self):
        result = []
        curr = self.head
        while curr.next.next:
            curr = curr.next
            result.append(curr.data)
        return result


    def reverse(self):
        result = []
        curr = self.tail
        while curr.prev.prev:
            curr = curr.prev
            result.append(curr.data)
        return result


    def getAt(self, pos):
        if pos < 0 or pos > self.nodeCount:
            return None

        if pos > self.nodeCount // 2:
            i = 0
            curr = self.tail
            while i < self.nodeCount - pos + 1:
                curr = curr.prev
                i += 1
        else:
            i = 0
            curr = self.head
            while i < pos:
                curr = curr.next
                i += 1

        return curr


    def insertAfter(self, prev, newNode):
        next = prev.next
        newNode.prev = prev
        newNode.next = next
        prev.next = newNode
        next.prev = newNode
        self.nodeCount += 1
        return True


    def insertAt(self, pos, newNode):
        if pos < 1 or pos > self.nodeCount + 1:
            return False

        prev = self.getAt(pos - 1)
        return self.insertAfter(prev, newNode)


    def popAfter(self, prev):
        curr = prev.next
        next = curr.next
        prev.next = next
        next.prev = prev
        self.nodeCount -= 1
        return curr.data


    def popAt(self, pos):
        if pos < 1 or pos > self.nodeCount:
            return None

        prev = self.getAt(pos - 1)
        return self.popAfter(prev)


    def concat(self, L):
        self.tail.prev.next = L.head.next
        L.head.next.prev = self.tail.prev
        self.tail = L.tail

        self.nodeCount += L.nodeCount


class PriorityQueue:

    def __init__(self):
        self.queue = DoublyLinkedList()


    def size(self):
        return self.queue.getLength()

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

    def enqueue(self, x):
        newNode = Node(x)
        curr = self.queue.head

        while curr.next.next and curr.next.data >= x:
            curr = curr.next
        self.queue.insertAfter(curr, newNode)

    def dequeue(self):
        return self.queue.popAt(self.queue.getLength())

    def peek(self):
        return self.queue.getAt(self.queue.getLength()).data


def solution(x):
    return 0