백준11286(파이썬) - 절댓값 힙

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

11286번: 절댓값 힙

• 파이썬에는 heapq라는 라이브러리가 있어서 쉽게 heap 구현을 할 수 있다.
• 파이썬의 heap은 기본적으로 최소 힙 (Min heap) 으로 구현 되어 있는데 이를 최대 힙이나 다른 조건의 heap으로 바꿔서 구현하려면 heap을 넣는과정에서 원래 값과, 조건값을 넣어주면 된다. 더 자세한 내용은 아래 게시물에서 참고하면 된다.

2021.05.19 - [Algorithm & Python/알고리즘 및 자료구조] - 자료구조 우선순위 큐(Priority Queue)와 힙(heap)

자료구조 우선순위 큐(Priority Queue)와 힙(heap)

 

그럼 이제 문제를 풀어보면 그 조건값에 절댓값을 넣어주면 되는 문제이다. 아래 코드를 보자.

 

• h라는 리스트에 i라는 데이터를 heap을 구현하면서 넣을게 라는 의미인데
• i를 넣지않고, (i,abs(i))를 넣어주면, abs(i)로 heap을 구현하게 된다.
• 그 다음에 출력을 하게 될 경우에는 (i,abs(i))에서 i를 출력해주면된다.

import heapq
import sys
input = sys.stdin.readline

n = int(input())
data = []
for _ in range(n):
    data.append(int(input()))

h = []
result = []
for i in data:
    if i == 0:
        if len(h)>0:
            result.append(heapq.heappop(h))
        else:
            result.append(0)
    else:
    # 이부분이 h라는 리스트에 i라는 데이터를 heap을 구현하면서 넣을게 라는 의미인데
    # i를 넣지않고, (i,abs(i))를 넣어주면, abs(i)로 heap을 구현하게 된다.
    # 그 다음에 출력을 하게 될 경우에는 (i,abs(i))에서 i를 출력해주면된다.
        heapq.heappush(h,(i,abs(i)))
print(result)
for i in result:
    if i == 0:
        print(0)
    else:
        print(i[1])