[프로그래머스] 이중우선순위큐

https://programmers.co.kr/learn/courses/30/lessons/42628

코딩테스트 연습 - 이중우선순위큐

heap을 두개 이용하는 문제입니다.

 

우선 문제부터 요약하면, 

숫자를 넣고, 최댓값을 없애고, 최솟값을 없애는 총 3가지 명령어가 있습니다. 이때, 모든 명령어들을 처리하고 난 후의 상태를 return 해주는 문제입니다.

실제 명령어가 생긴 형태는 다음과 같고 좀더 자세한 내용은 실제 문제 링크를 이용해서 읽어 보는 것을 추천합니다.

 

<Solution>

아이디어는 두 heap을 어떻게 동기화 시킬 것이냐가 중요합니다.

 

잘못된 풀이들에는

1. del[index] 로 마지막 것을 그냥 없애줌 (min heap에서 가장 마지막 index가 최댓값이 아님) 2. remove로 삭제하는 경우 (다시 heapify 해주지 않으면 오류가 생길수 있음)

우선 max, min heap을 각각 둔다고 생각해봅시다. 만약 max heap에서 원소가 사라지게 되면, min heap에서도 사라져야 합니다. 이것을 처리해줄 때, min heap의 마지막 원소가 max값이 아니므로 이렇게 삭제를 하게 되면 오류가 발생합니다. 

다음으로 만약 remove를 통해 value로 삭제하게 되면, 다시 heap을 heapify해주어야 합니다. 만약 이 과정이 없다면 오류가 발생하게 됩니다.

왜 heapify를 해야하는가를 설명하려면 heap의 소스코드의 작동원리를 파악해야 하는데 추후에 공부해서 포스팅해보도록 하겠습니다. 

(여기에서 궁금증이 들었는데 특정 원소를 넣거나 뺄때 내부적으로 heap에는 어떤 과정이 일어나고 어떻게 heap의 성질을 유지하고 있는지 -> 대략적으로 heap에는 siftup과 siftdown을 이용한다고 되어 있는데 자세한 내용은 공부해서 추후에 포스팅해보도록 하겠습니다.)

 

아이디어

Stack overflow에 heap에서 만약 원소의 priority가 수정되면 어떻게 처리해야하는가에 대한 질문에서 참고한 아이디어입니다. 

실제로 삭제를 하지 않고 marking만 해둔다음 pop이 일어날 때, invalid한 경우를 무시하는 것입니다. 

또한 min heap과 max heap의 동기화는 list와 같은 mutable 자료구조를 이용하여, 같은 객체를 넣어준 다음 한쪽에서 pop 된 원소를 False로 마킹 하는 형태로 구현하였습니다. 

 

간단한 예시를 참고하면 이해하기가 편할 것입니다.

["I 16", "I -5643", "D -1", "D 1", "D 1", "I 123", "D -1"]

다음의 명령어가 들어오면 min, max heap의 상태는 다음과 같이 진행됩니다. 

---------------------------------------------
(init)
max_heap
[]
min_heap
[]
---------------------------------------------
operation = I 16
max_heap
[[-16, [16, True]]]
min_heap
[[[16, True]]]
---------------------------------------------
operation = I -5643
max_heap
[[-16, [16, True]], [5643, [-5643, True]]]
min_heap
[[[-5643, True]], [[16, True]]]
---------------------------------------------
operation = D -1
max_heap
[[-16, [16, True]], [5643, [-5643, False]]]
min_heap
[[[16, True]]]
---------------------------------------------
operation = D 1
max_heap
[[5643, [-5643, False]]]
min_heap
[[[16, False]]]
---------------------------------------------
operation = D 1
max_heap
[[5643, [-5643, False]]]
min_heap
[[[16, False]]]
---------------------------------------------
operation = I 123
max_heap
[[-123, [123, True]], [5643, [-5643, False]]]
min_heap
[[[16, False]], [[123, True]]]
---------------------------------------------
operation = D -1
max_heap
[[-123, [123, False]], [5643, [-5643, False]]]
min_heap
[]

실제 코드 구현은 아래와 같습니다

import heapq

def solution(operations):
    max_heap = []
    min_heap = []
    total_element = 0
    for operation in operations:
        op , num = operation.split()
        num = int(num)
        # print('---------------------------------------------')
        # print(f'max_heap\n{max_heap}')
        # print(f'min_heap\n{min_heap}')
        # print(operation)
        # print('---------------------------------------------')
        if op == 'I':
            # make list [num, available] (true -> available)
            common_append = [num, True]
            heapq.heappush(min_heap,[common_append])
            heapq.heappush(max_heap,[-num, common_append])
            total_element +=1
        else: # op == 'D'
            if total_element == 0:
                continue
            if num == 1:
                while(1):
                    element = heapq.heappop(max_heap)
                    if element[1][1] == False:
                        continue
                    else:
                        element[1][1] = False
                        break
                total_element -=1
            else:
                while(1):
                    element = heapq.heappop(min_heap)
                    if element[0][1] == False:
                        continue
                    else:
                        element[0][1] = False
                        break
                total_element -=1
    answer = []
    # get max element
    if len(max_heap) == 0:
        return [0,0]
    else:
        for _ in range(len(max_heap)):
            e = heapq.heappop(max_heap)
            if e[1][1] == True:
                answer.append(e[1][0])
                break
        if len(answer) == 0:
            return [0,0]

    # get min element
    for _ in range(len(min_heap)):
        e = heapq.heappop(min_heap)
        if e[0][1] == True:
            answer.append(e[0][0])
            break
    return answer

 

<참고자료 & 추후에 읽어보기>

https://stackoverflow.com/questions/10162679/python-delete-element-from-heap

Python: delete element from heap

https://en.wikipedia.org/wiki/Heap_%28data_structure%29

Heap (data structure) - Wikipedia

https://github.com/python/cpython/blob/main/Lib/heapq.py

GitHub - python/cpython: The Python programming language

https://stackoverflow.com/questions/46996064/how-to-update-elements-within-a-heap-priority-queue

How to update elements within a heap? (priority queue)

https://docs.python.org/3.5/library/heapq.html#priority-queue-implementation-notes

8.5. heapq — Heap queue algorithm — Python 3.5.9 documentation