[Python/DailyAlgo, 백준] 92. 우선순위 큐, 11279. 최대 힙, 11286. 절댓값 힙

문제 접근 및 공부 내용, 풀이는 모두 하단 코드에 "주석"으로 포함되어 있으니 참고해주세요.

문제 유형 보기

힙

https://dailyalgo.kr/ko/problems/92

https://www.acmicpc.net/problem/11279

https://www.acmicpc.net/problem/11286

---

풀이

92. 우선순위 큐

from heapq import heappop, heappush
def solution(queries):
    heap = []
    answer = []
    for query in queries:
        # pop
        if query == 0:
		        # answer.append(heappop(heap) if heap else 0)
		        # 위처럼 삼항연산자 사용할 수도 있음.
            if heap:
                answer.append(heappop(heap))
                continue
            answer.append(0)
            continue
            
        # push
        heappush(heap, query) 

    return answer

11279. 최대 힙

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

# push, pop(maxpop) ADT를 가지는 최대 힙을 구현해라.

n = int(input())
heap = []

for _ in range(n):
    x = int(input())
    # pop -> 여기서 print 수행하면 됨.
    if x == 0:
        if heap:
            print(-heappop(heap))
            continue

        print(0)
        continue
    # push
    heappush(heap, -x)

11286. 절댓값 힙

from heapq import heappush, heappop
import sys
input = sys.stdin.readline

# 흠, 일단 시간복잡도 최대 nlog(n) 하면 최악의 경우에도 뭐 천만대 정도 돼서 괜찮겠고.
# 입력 : 연산개수, 둘째 줄부터 연산 정보를 나타내는 정수 x가 주어짐.
# 출력 : 0이 주어진 횟수만큼 pop한 결과 정수를 출력

# 0이면 pop을 하는데 비어있으면 0 출력
# 0아니면 최소 힙 변형으로 절대값이 가장 작은 값 pop해서 출력하는데,
# 절댓값이 가장 작은 게 여러개면 더 작은 값(음수)를 출력함.

# 이거 튜플 형식으로 넣어야겠느데, (abs(x), x)로 넣으면 되겠는데?

heap = []
n = int(input())
for _ in range(n):
    x = int(input())
    # pop
    if x == 0:
        if heap:
            print(heappop(heap)[1])
            continue
        print(0)
        continue
    # push
    heappush(heap, (abs(x), x))