백준 11286 절댓값 힙

문제

---

솔루션

import heapq
import sys
input = sys.stdin.readline

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

---

깨달은 점

N = int(input())
heap=[]
for _ in range(N):
    x = int(input())
    if x != 0:
        heap.append(x)
    else:
        if len(heap)==0:
            print(0)
        else:
            for i in heap:
                min=i
                if abs(i)<abs(min):
                    min = i
            print(i)
            heap.remove(i)

이렇게 하려했는데 시간초과가 떴다.

힙을 import해서 해야한다.

 

여기서 필요한 구조 heapq이다.

import heapq

heapq는 기본적으로 최소 힙(min-heap)을 구현한다.

최소 힙에서는 가장 작은 값을 우선적으로 처리하는 자료구조이다. 

heapq.heappush(heap, (abs(x), x))

heapq.heappush()는 값을 힙에 추가하는 함수

• 이 함수는 자동으로 힙의 특성에 맞게 데이터를 정렬하여 삽입한다.
• 절댓값이 작은 값을 우선적으로 꺼내기 위해 값을 튜플 (abs(x), x)로 삽입한다.
• 튜플의 첫 번째 값인 abs(x)를 기준으로 비교되게 하기 위함
• heapq는 먼저 절댓값을 기준으로 비교하고, 절댓값이 같으면 두 번째 값인 x를 기준으로 비교

print(heapq.heappop(heap)[1])

heapq.heappop()은 힙에서 가장 작은 값을 꺼내는 함수

heappop은 가장 작은 첫 번째 값을 가진 튜플을 반환 -> 가장 작은 절댓값을 가진 튜플을 반환

반환된 튜플에서 두 번째 값인 x를 사용하려면 [1]을 사용해서 원래 값을 꺼냄