11286 절댓값 힙 _python

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

11286번: 절댓값 힙

절댓값 hip

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

문제 접근

그냥 힙 사용하듯이 사용하면 된다.

heap에 넣을때 최대힙을 만들때 쓰는 방법이 2가지있는데,

첫 번째는 값을 넣을때 (-)로 넣고 (-)로 빼는방법이 있고,

두 번째는 값을 넣고 뺄때 튜플을 사용해서 넣는 방법이 있다.

이 사실만 알면 쉽게 접근할 수 있다.

두 번째 방법인 튜플을 사용하면 된다.

heapq.heappush((abs(x), x))로 넣고 빼면 된다.

 

처음에 의아하던게 절대값으로 넣는다 한들 같은 값이면 작은값을 우선으로 출력해야하는데 힙 자체를 import없이 구현해야하나 했는데, 튜플로 넣고 첫번째가 같다면 두번째 값을 비교한다

그래서 그냥 튜플로 넣으면 해결된다.

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

코드

import heapq
import sys
input = sys.stdin.readline

"""
튜플형태로 힙 사용
"""

N = int(input())
heap = []
for _ in range(N):
    x = int(input())
    if x:
        heapq.heappush(heap, (abs(x), x))
    else:
        try:
            print(heapq.heappop(heap)[1])
        except:
            print(0)

136ms