프로그래머스 43268] 이중우선순위큐 - 파이썬

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21

def solution(operations):
    import heapq
    heap = []
    for i in range(len(operations)):
        alphabet, number = operations[i].split(" ")
        if alphabet == "I":
            # 힙에 추가
            heapq.heappush(heap, int(number))
        # 비어있는 경우 index error 이기 때문에 and heap
        elif alphabet == "D" and heap:
            if number == "1":
                # 최대값 삭제
                heap.remove(max(heap))
            elif number == "-1":
                # 가장 작은 원소 pop 후 리턴
                heapq.heappop(heap)

    if heap:
        return [ max(heap), heap[0] ]
    else:
        return [0,0]

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68

import heapq

REMOVED = "r"


class DoublePriorityQueue:

    def __init__(self):

        self.entry_finder = {}
        self.min_heap = []
        self.max_heap = []
        self.cnt = 0

    def _check_empty(self, q) -> bool:
        while q and q[0][1] == REMOVED:
            heapq.heappop(q)
        if not q:
            return True
        return False

    def insert(self, v):
        vid = self.cnt
        min_ele, max_ele = [v, vid], [-v, vid]
        heapq.heappush(self.min_heap, min_ele)
        heapq.heappush(self.max_heap, max_ele)
        self.entry_finder[vid] = [min_ele, max_ele]
        self.cnt += 1

    def pop_min(self):
        is_empty = self._check_empty(self.min_heap)
        if not is_empty:
            value, vid = heapq.heappop(self.min_heap)
            entries = self.entry_finder.pop(vid)
            entries[1][1] = REMOVED

    def pop_max(self):
        is_empty = self._check_empty(self.max_heap)
        if not is_empty:
            value, vid = heapq.heappop(self.max_heap)
            entries = self.entry_finder.pop(vid)
            entries[0][1] = REMOVED

    def get_min(self):
        if not self._check_empty(self.min_heap):
            return self.min_heap[0][0]
        return 0

    def get_max(self):
        if not self._check_empty(self.max_heap):
            return - self.max_heap[0][0]
        return 0


def solution(operations):
    dpq = DoublePriorityQueue()

    for each in operations:
        op, num = each.split(" ")
        num = int(num)
        if op == "I":
            dpq.insert(num)
        elif op == "D" and num == -1:
            dpq.pop_min()
        else:
            dpq.pop_max()

    return [dpq.get_max(), dpq.get_min()]