[Python]백준11286::절댓값 힙 문제풀이

Solution

👉 minheap을 사용

👉 x가 0 이 아닐 때 heap 에다가 튜플(절대값, 진짜값) 로 값을 넣는다. (자동으로 minheap 형태로 된다.)

👉 x가 0 일때 출력을 해줘야 하는데, 만약 들어있는 값이 없다면 0을 출력해주고 그게 아닐 시에는 pop 해주면 된다.(자동으로 가장 위의 노드인 min 값이 팝 된다.) - 이때 pop 시키면서 해당 튜플 값을 k 변수에 저장해두었다가 k의 인덱스 1번 값을 출력해준다.(절대값 아닌 진짜 값!)

 

TIP

👉 import heapq

👉 sys.stdin.readline

👉 heapq.heappush(리스트, 값)    / heapq.heapop(리스트)

👉 heapq 는 리스트를 선언하고 그 리스트를 인자로 넣어 주는 식으로 사용한다는 점! 

 

 

정답 풀이

# 절댓값 힙

import heapq,sys

pq = []

n = int(sys.stdin.readline()) # 1<=  <=100000

for i in range(n):
    x = int(sys.stdin.readline()) # -2^31 ~ 2^31
   
    if(x == 0):
        # 배열에서 절댓값 가장 작은 값 출력
        if(len(pq)==0):
            print(0)
        else:
            k = heapq.heappop(pq)
            print(k[1])
    else:
        # x라는 값 넣기
        heapq.heappush(pq,(abs(x),x))

 

---

 

👇파이썬으로 문제를 풀 때 사용하는 자료구조 구현 방법 및 라이브러리를 정리한 글입니다.

2021.05.04 - [Algorithm/Python] - [Python] 문제 풀 때 알고리즘에 주로 사용하는 자료구조 활용법을 알아보자!

[Python] 문제 풀 때 알고리즘에 주로 사용하는 자료구조 활용법을 알아보자!