[Python][힙] 프로그래머스 - 이중우선순위큐(LEVEL3)

문제출처 - https://programmers.co.kr/learn/courses/30/lessons/42628

프로그래머스

내 풀이

import heapq

# 힙에서 원소 뺐으면 다른 힙 초기화하고 다시 넣어줌
def changeHeap(heap):
    h = []
    for num in heap:
        heapq.heappush(h, -num)
    return h

def solution(operations):
    answer = []  # [최댓값, 최솟값]
    minheap = []
    maxheap = []

    for o in operations:
        command, num = o.split(' ')
        num = int(num)
        if command == 'I':
            heapq.heappush(minheap, num)
            heapq.heappush(maxheap, -num)
        elif command == 'D':
            try:
                if num == 1:  # 최댓값 삭제
                    heapq.heappop(maxheap)
                    minheap = changeHeap(maxheap)
                else:  # 최솟값 삭제
                    heapq.heappop(minheap)
                    maxheap = changeHeap(minheap)
            except:
                continue

    if len(maxheap) != 0:
        answer.append(-maxheap[0])
    else:
        answer.append(0)
    if len(minheap) != 0:
        answer.append(minheap[0])
    else:
        answer.append(0)
    return answer

설명

 

Python의 heapq 라이브러리를 사용해 이중우선순위큐 문제를 풀었다.

 

최대힙과 최소힙을 저장하는 배열을 2개 만들어서

 

최대값을 삭제하는 경우, 최소힙을 초기화시키고 최대값 삭제한걸 뺀 원소들을 다시 배열에 넣어줬다. 

 

 

다른 사람 풀이

def solution(operations):
	answer = []
    for i in operations:
        a, b = i.split()
        if a == 'I':
            answer.append(int(b))
        else:
            if len(answer) > 0:
                if b == '1':
                    answer.pop()
                else:
                    answer.pop(0)
            else:
                pass
      	answer.sort()
    
    if len(answer) == 0:
    	return [0, 0]
    else:
    	return [max(answer), min(answer)]

무조건 힙 자료구조를 이용해서 풀어야 통과인줄 알았는데 아니었음...

 

그냥 배열쓰고 매번 정렬시켜줘도 됨

 

 

더 간단한 힙을 이용한 풀이

import heapq

def solution(operations):
    h = []

    for i in operations:
        a, b = i.split()
        if a == 'I':
            heapq.heappush(h, int(b))
        else:
            if len(h) > 0:
                if b == '1':
                    h.pop(h.index(heapq.nlargest(1, h)[0]))
                else:
                    heapq.heappop(h)

    if len(h) == 0:
        return [0, 0]
    else:
        return [heapq.nlargest(1, h)[0], h[0]]

heapq의 nlargest함수를 사용하면 나처럼 최대힙, 최소힙 배열을 나누지 않아도 된다.

 

nlargest(n, heap) 함수는 n개의 가장 큰 값들로 이루어진 리스트를 반환한다. 즉, 첫번째 인자에 찾고싶은 최대값의 개수를 넣어주면 됨!!

 

첫번째 풀이말고 위의 풀이대로 체점하면 실행시간이 좀 더 짧아짐!!

 

 

📌heapq 라이브러리 참고 - https://python.flowdas.com/library/heapq.html

heapq --- 힙 큐 알고리즘 — 파이썬 설명서 주석판

📌다른 풀이 참고 - https://codedrive.tistory.com/54