#11279. 최대 힙

백준의 실버2티어 문제이다. 스터디에서 했던 힙 유형을 복습하기 위해 풀게 되었다.

참고로 #1927. 최소 힙과 아주 유사하다.

📖Problems

널리 잘 알려진 자료구조 중 최대 힙이 있다. 최대 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.

배열에 자연수 x를 넣는다.
배열에서 가장 큰 값을 출력하고, 그 값을 배열에서 제거한다.

프로그램은 처음에 비어있는 배열에서 시작하게 된다.

입력

첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 큰 값을 출력하고 그 값을 배열에서 제거하는 경우이다. 입력되는 자연수는 231보다 작다.

출력

입력에서 0이 주어진 회수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 큰 값을 출력하라고 한 경우에는 0을 출력하면 된다.

예제 입력 1

예제 출력 1

🔍Institution

priority queue를 사용하면 된다. 이는 python에서 heapq모듈을 통해 구현한다.

또한 이 문제는 #11279. 최대 힙 문제와 유사하다는 것을 미리 알린다.

🔍Concepts

📌한 개의 정수를 입력받을 때

  
import sys
a = int(sys.stdin.readline())

파이썬으로 힙 자료구조

참고자료 : https://www.daleseo.com/python-heapq/, https://redcrow.tistory.com/487

Heap

stack : LIFO(Last In First Out)
queue : FIFO(First In First Out)
하지만 쌓을 때부터 순서를 고려해야 하는 경우가 존재한다. Stack과 Queue가 넣은 순서대로 꺼낸다면, **Priority Queue**는 우선순위가 존재해서 우선순위가 높은 데이터부터 꺼내도록 구현된 자료구조이다.
Heap 은 Priority Queue와 같이 우선 순위가 존재하는 자료구조이다.
Heap : 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전이진트리
- Max Heap
- Min Heap

Heap을 사용하는 이유

배열에서 최대 최소 값을 찾으려면 O(n) 이 걸리는데 비해 Heap은 O(log n)으로 성능이 더 좋다.
배열에서 데이터의 최대, 최소 값을 찾기 위해 사용한다

파이썬에서 Heap 기능 사용하기

module import
1 import heapq
최소 힙 생성
1 heap = []

힙에 원소 추가 : heappush(list, item)

  
 from heapq import heappush
    
 heappush(heap, 4)
 heappush(heap, 1)
 heappush(heap, 7)
 heappush(heap, 3)
 print(heap)
 # 결과 : [1,3, 7, 4]
 # 시간복잡도 : O(log(n))

힙에서 원소 삭제 : heappop(list)

  
 from heapq import heappop
    
 print(heappop(heap))
 print(heap)
 '''
 1
 [3, 4, 7]
 '''

기존리스트를 힙으로 변환 : 이미 원소가 들어 있는 경우 → heapify()

  
 from heapq import heapify
    
 heap = [4, 1, 7, 3, 8, 5]
 heapify(heap)
 print(heap)
 # 결과 :[1, 3, 5, 4, 8, 7]

max heap
heapq 모듈은 min heap 기능만 동작함.
- (우선순위, 값) 구조의 튜플을 힙에 추가한 후 삭제하면 된다.
- 힙에서 값을 읽어 올 때는
  - 튜플에서 인덱스 1에 있는 값을 취하면 된다.(우선순위에는 관심 x)
  - 또는 heappop() 앞에 -1을 취하면 된다.

  
from heapq import heappush, heappop

nums = [4, 1, 7, 3, 8, 5]
heap = []

for num in nums:
  heappush(heap, (-num, num))  # (우선 순위, 값)

while heap:
  print(heappop(heap)[1])  # index 1

'''
다른 방법
while heap3:
    print(-heappop(heap))
'''

값을 마이너스(-)로 바꾸면 가장 큰 값이 맨 처음에 나온다.
위의 Max heap 만드는 것을 활용해 코드를 구현한다.

🔍Approach

🚩My submission

조건

0 : 배열에서 가장 큰 값 출력하고 그 값을 배열에서 제거 (heappop())
다른 숫자 : 배열에 push (heappush())

🚩Flow

연산 개수 n을 입력받는다. heap리스트를 만든 후 heapify 시킨다.
정수 num을 입력받는다.
만약 num이 0일 경우에는 heappop()을 수행한다. 이때 가장 큰 값을 pop해야 하므로 print할 때 -1을 취한다.
1. 또한 이 과정에서 heap이 비어 있을 경우에는 0을 출력하도록 한다.
num이 0이 아닐 경우(0을 제외한 수)일 경우, heap에 push한다. 이때, max값을 구해야 하므로 -를 붙여서 push한다.(heappush(heap, -num))
입력받은 n이 0이 될 때까지 반복하며, 반복할 때마다 n을 -1해준다.

  
import heapq
import sys

n = int(sys.stdin.readline())
heap = []

while n > 0:
    num = int(sys.stdin.readline())
    n -= 1
    if num == 0:
        if len(heap) == 0:
            print(0)
            continue
        print(-heapq.heappop(heap))
       
    else:
        heapq.heappush(heap, -num)

🚩Others submission

https://claude-u.tistory.com/152

  
import sys
import heapq

numbers = int(input())
heap = []

#Max Heap
for _ in range(numbers):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, (-num))
    else:
        try:
            print(-1 * heapq.heappop(heap))
        except:
            print(0)

heapq를 활용하지만 이 함수는 min heap만을 지원한다. 따라서 num을 음수로 만들어줘 최대값을 출력한다.

💡TIL

스터디에서 ‘힙’ 부분의 진도를 나갔기 때문에 복습하기 위해 해당 문제를 풀었다.

heap에 대해 복습하면서, 이전 최소 힙에서 heap이란 어떤 것인지 어떻게 활용하면 좋은지 알게 되었으며 해당 문제에서는 max heap, 즉 최대를 구하는 힙을 풀며 힙을 활용하는 방식을 배우게 되었다.

heap : 우선 순위가 존재하는 자료구조, 최대최소 문제 풀 때 활용됨

  
  # max heap
  for num in nums:
    heappush(heap, (-num, num))  # (우선 순위, 값)
    
  while heap:
    print(heappop(heap)[1])  # index 1
    
  '''
  다른 방법
  while heap3:
      print(-heappop(heap))
  ''' 

백준 - 11279. 최대 힙 (MJ)