힙_이중우선순위큐_Python

문제 설명

이중 우선순위 큐는 다음 연산을 할 수 있는 자료구조를 말합니다.

명령어수신 탑(높이)

이중 우선순위 큐가 할 연산 operations가 매개변수로 주어질 때, 모든 연산을 처리한 후 큐가 비어있으면 [0,0] 비어있지 않으면 [최댓값, 최솟값]을 return 하도록 solution 함수를 구현해주세요.

제한사항

• operations는 길이가 1 이상 1,000,000 이하인 문자열 배열입니다.
• operations의 원소는 큐가 수행할 연산을 나타냅니다.
  • 원소는 “명령어 데이터” 형식으로 주어집니다.- 최댓값/최솟값을 삭제하는 연산에서 최댓값/최솟값이 둘 이상인 경우, 하나만 삭제합니다.
• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

입출력 예

operationsreturn

입출력 예 설명

16을 삽입 후 최댓값을 삭제합니다. 비어있으므로 [0,0]을 반환합니다.
7,5,-5를 삽입 후 최솟값을 삭제합니다. 최대값 7, 최소값 5를 반환합니다.

---

접근방법

heapq로 우선순위 큐를 구현한다.

빈 리스트에 heapq 메소드를 이용해 값을 관리하면 리스트는 heap 속성을 만족하게 된다(defult: min)

주어진 배열은 문자열이기에 명령과 값으로 분류 하고, min_heap이 int 요소를 갖게 하기 위해 

str data => int data로 변환해준다.

 

최댓값을 삭제하는 경우 

min_heap의 맨 마지막 인덱스가 최대값임을 이용

 

최솟값을 삭제하는 경우

heapq 는 기본적으로 min_heap이기에 heappop()로 가장 맨 앞의 인덱스값이 최솟값이다.

이때 data를 str 타입으로 사용하면 ㄱㄴㄷ 순과 같이 사전적 의미로 정렬 + 오름차순이 기본 값이 되기 때문에

-45 보다 -645가 더 큰값으로 인식하게 된다.

 

우선순위 큐에 데이터 삽입

 

만약 heap이 비어있는 경우를 고려해주었다.

2, 4, 6테스트 케이스 실패

import heapq

def solution(operations):
    answer = []
    min_heap = []
    
    for value in operations:
        order, data = value.split()
        data = int(data)
        
        if order == "D" and data == 1:
            if min_heap:
                # print('===555')
                min_heap.pop(-1)

        elif order == "D" and data == -1:
            heapq.heappop(min_heap)
        else:
            heapq.heappush(min_heap, data)

    

    if not min_heap:
        return [0,0]

    return min_heap[-1], min_heap[0]

---

개선

먼저 테스트 케이스 2, 4의 경우

질문을 참고하여 보니 

• 빈 큐에 데이터를 삭제하라는 연산이 주어질 경우, 해당 연산은 무시합니다.

라는 조건을 최댓값 삭제하는 경우만 적용해주었었다. 최솟값도 어짜피 삭제인데 말이다.

# 최댓값 삭제
        if order == "D" and data == 1:
            if min_heap:
                min_heap.pop(-1)
        # 최솟값 삭제
        elif order == "D" and data == -1:
            if min_heap:
                heapq.heappop(min_heap)

---

개선_2

여기서 굉장히 중요한 내용을 학습할 수 있었다.

힙 구조는 우선순위가 높은 값이 루트 노드에 위치하게 되는 것을 보장하는 자료구조이다.

여기서는 어디에도 맨 마지막 리프 노드(요소)가 최댓값임을 보장하지 않는다는 것이었다.

힙 구조는 가장 우선순위가 높은 값이 먼저 pop 되는 것을 보장하는 자료구조이다.
pq[0]가 가장 우선순위가 높은 값(가장 작은값)인 것은 맞지만, 나머지 값에 대한 정렬은 보장하지 않는다는 의미이다. (프로그래머스 질문 답변: softmare님)

그냥 당연하게 맨 마지막 요소가 최댓값이지라는 생각을 가지고 있었었다.

힙 속성을 되새겨보면 (참고: 힙_1 :: muntari Log (tistory.com))

1. 형태 속성 : 힙은 완전 이진 트리여야 한다.
2. 힙 속성 : 모든 노드의 데이터는 자식 노드들의 데이터보다 크거나 작아야 한다.

import heapq

pq = []
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 5)
heapq.heappush(pq, 2)
heapq.heappush(pq, 4)
print(pq)
# [1, 2, 5, 3, 4]

루트 노드 1은 최솟값임이 확실히 보장되나 모든 노드의 데이터는 자식 노드보다 작기만 하면 된다.

즉, 완전 이진 트리이면서 위 조건을 만족해야하기에 아래와 같은 트리 구조를 갖는다.

마지막 인덱스 4는 최댓값이라는 보장이 없다.

	    1
	2       5
    3       4

1. min_heap[-1]이 항상 최대값이라는 보장이 없다 => 

따라서 최댓값 삭제부분도 수정하고 리턴 값도 수정하였다.

import heapq

def solution(operations):
    min_heap = []
    for value in operations:
        order, data = value.split()
        data = int(data)
        # 최댓값 삭제
        if order == "D" and data == 1:
            if min_heap:
                max_value = max(min_heap)
                min_heap.remove(max_value)
        # 최솟값 삭제
        elif order == "D" and data == -1:
            if min_heap:
                heapq.heappop(min_heap)
        # 큐 데이터 삽입
        else:
            heapq.heappush(min_heap, data)
    
    # heap이 비어있는 경우
    if not min_heap:
        return [0, 0]
    return max(min_heap), min_heap[0]

---

시간복잡도

배열의 길이를 N이라 할때

힙은 N개의 노드와 lgN의 높이를 갖는다.

배열은 큐가 수행할 연산을 나타냄 => O(N)

split() => 주어진 문자열 모두 탐색 O(N)

max() => O(N)

remove() => O(N)

heappop() => O(lgN)

heappush() => O(lgN)

 

총시간복잡도는 O(N^2)? 

우선순위 큐를 사용하는 이유는 삽입과 삭제를 O(N)이 아닌 O(lgN)의 효율로 사용하기 위함이다.

종합해볼때 N^2로 예상되는데.. 보시다시피 효율이 굉장히 좋다.

그냥 문제에서 원한 답을 찾아서 그런건지 모르겠다.

추후 질문 답변을 확인해보도록 하자