[Programmers] 이중우선순위큐

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

프로그래머스

 

풀이

from heapq import heapify, heappop, heappush

def solution(operations):
    answer = []
    queue = []
    heapify(queue)
    for operation in operations:
        left, right = operation.split(" ")
        if left == 'I': # 큐에 주어진 숫자 삽입
            heappush(queue, int(right))
        elif right == '1': # 큐에서 최댓값을 삭제
            if len(queue) == 0:
                continue
            if len(queue) == 1:
                heappop(queue)
            else:
                # 최대 힙 만들어주기
                reverse_sign = lambda x:x*(-1)
                max_heap = list(map(reverse_sign, queue))
                heapify(max_heap)
                max_heap = list(map(reverse_sign, max_heap))
                max_heap.pop(0) # 최댓값 삭제
                heapify(max_heap)
                queue = max_heap
        else: # 큐에서 최솟값을 삭제
            if len(queue) >= 1: # 최솟값 삭제
                heappop(queue)
    
    if len(queue) == 0:
        answer = [0, 0]
    else:
        answer.append(max(queue))
        answer.append(queue[0])
    return answer

처음에 queue가 비었을 때도 pop을 해주려 해서 시간낭비를 좀 했다. 꼭 꼭 조건 잘 확인하자.

그리고 힙 자료구조에 대해서 잘못 알고 있었던게 있었다.

힙 자료구조는 가장 높은(혹은 가장 낮은) 우선순위(e.g., 최댓값, 최솟값)를 가지는 노드를 빠르게 찾아내기 위해 고안된 *완전 이진트리(Complete Binary Tree) 기반의 자료구조이다. 따라서 가장 높은(또는 가장 낮은) 우선순위를 가지는 노드가 항상 루트 노드(root node)에 오는 게 특징

으로, 맨 앞의 수 (즉, 루트 노트)가 최솟값인건 보장하나, 배열 안의 수들이 오름차순으로 정렬되어 있는게 아니다.

그래서 마지막 answer을 만들어주는 부분에서 자꾸 최댓값을 queue[-1] 이걸로 넣어주려 해서 시간을 너무 낭비했다 😅

 

 

복습할 것

1. 최대 힙 만드는 방법 ⭐️ 두 번째 방법 기억!

# 최대 힙 만들어주기
reverse_sign = lambda x:x*(-1)
max_heap = list(map(reverse_sign, queue))
heapify(max_heap)
max_heap = list(map(reverse_sign, max_heap))
max_heap.pop(0) # 최댓값 삭제


# 더 효율적인 방법 !!!!! 꼭 기억하자.
heap = heapq.nlargest(len(heap), heap)[1:]
heapq.heapify(heap)

 

2. 힙 자료구조의 특징

맨 앞의 수 (즉, 루트 노트)가 최솟값인건 보장하나, 배열 안의 수들이 오름차순으로 정렬되어 있는게 아니다.

 

예시)

명심하자 ...

 

개선된 풀이!

from heapq import heapify, heappop, heappush, nlargest

def solution(operations):
    answer = []
    queue = []
    heapify(queue)
    for operation in operations:
        left, right = operation.split(" ")
        if left == 'I': # 큐에 주어진 숫자 삽입
            heappush(queue, int(right))
        elif right == '1': # 큐에서 최댓값을 삭제
            if len(queue) == 0:
                continue
            if len(queue) == 1:
                heappop(queue)
            else:
                # 최대 힙 만들어주기
                queue = nlargest(len(queue), queue)[1:]
                heapify(queue)
        else: # 큐에서 최솟값을 삭제
            if len(queue) >= 1: # 최솟값 삭제
                heappop(queue)
    
    if len(queue) == 0:
        answer = [0, 0]
    else:
        answer.append(max(queue))
        answer.append(queue[0])
    return answer