[힙] 이중우선순위 큐 with Python (★)

문제

 

참고한 코드

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]]

> 참고한 블로그

https://johnyejin.tistory.com/135

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

> 정말 대단...

> heapq 모듈에 대한 설명

https://python.flowdas.com/library/heapq.html

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

 

내가 해석한 코드 설명

h = []

> 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)

> 값이 저장된 operations을 for문(반복문)을 사용하여 하나씩 값을 받게 합니다.

> i.split() 함수를 사용하여 a, b로 각 값을 받게 합니다.

> a == 'I' 일때는 값을 h변수에 넣으면 되는데, 최소, 최대값을 빼기 위해서는 heapq 모듈에서 heapq.heappush 를 사용했습니다.

> heapq.heappush 를 사용하면 출력하면 최소값이 먼저 빠지게 된다.

> 그리고 else문에는 a가 D일 경우이므로, b == -1이면 최소값 제거, b == 1이면 최댓값 제거이다.

> if len(h) > 0 을 사용한 이유는 최소값, 최대값 제거를 하다보면 h 리스트가 빈 값일 경우가 존재한다. 그 경우를 대비해서 len(h) >0 일때만 아래 코드가 수행되게 작성을 한 것이다.

> 다시 한 번 if - else문을 사용하여 b == 1일 때 , h.pop(h.index(heapq.nlargest(1, h)[0])) 을 사용하게 해준다.

> 먼저 heapq.nlargest(1, h) 의 의미는 h 리스트에서 최대값 1개를 출력하는 것이다. 만약 2개의 가장 큰 값이면 heapq.nlargest(2, h) 를 작성하면 된다.

> 이 코드는 리스트로 출력이 되기 때문에 heapq.nlargest(1, h)[0] 을 통해서 값만 출력하기 위해서 뒤에 [0]을 작성한 것이다.

> h.index() 를 해주면 h 변수에 있는 값의 index 위치를 출력시켜준다.

> 그 index를 h.pop(index)를 해주면 h 변수에서 해당하는 index 값이 빠져나가게 된다.

> 그러면, 최종적으로 h변수에서의 최댓값이 빠져나가게 되는것이다.

> else 문에서 heapq.heappop()을 해주면 h변수에 최소값이 출력하게 된다.

 

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

> len(h) == 0 일때는 최종 h 변수가 빈 값일 경우에는 [0, 0] 을 출력하라고 했으므로 이렇게 작성한 것이다.

> 그게 아닐 경우에는 [최댓값, 최소값] 형태로 출력하라고 했으므로, 다음과 같이 작성한 것이다.