[백준/Python] 11279번 최대 힙

---

문제

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

---

문제풀이(시간초과)

# 시간초과

n = int(input())

array = []

for i in range(n):

    x = int(input())

    if x > 0:

        array.append(x)

    elif x == 0:

        if len(array) == 0:

            print(0)

        else:

            print(max(array))

            array.remove(max(array))

 

리스트로 문제를 풀었더니 시간초과가 나타났다.

아무래도 remove()의 시간 복잡도가 O(N)이 걸리기 때문인 듯하다.

---

정답(Heap)

import heapq

n = int(input())

max_heap = []

for i in range(n):

    x = int(input())

    if x > 0:

        heapq.heappush(max_heap, -x)

    elif x == 0:

        if len(max_heap) == 0:

            print(0)

        else:

            if max_heap:

                print(-heapq.heappop(max_heap))

            else:

                print(0)

 

Heap(힙) 이란?

완전 이진 트리의 일종으로 우선순위 큐를 위하여 만들어진 자료구조이다.

여러 개의 값들 중에서 최댓값이나 최솟값을 빠르게 찾아내도록 만들어진 자료구조이며, 힙은 기본적으로 최소 힙을 사용한다. 따라서 최대 힙을 사용할 때는 음수를 저장하는 방법을 사용한다.

• heappush(heap, item) : heap에 item 추가
• heappop(heap) : heap에서 가장 작은 원소를 pop & 리턴한다. 비어 있는 경우 IndexError가 호출된다.