[algorithm] 백준 11279 - 최대 힙

[algorithm] 백준 11279 - 최대 힙

 

안녕하세요. 심심한 코딩쟁이입니다.

 

오늘은 백준 11279번 문제 - 최대 힙 의 풀이를 살펴보도록 하겠습니다.

 

풀이에 사용한 언어는 Python3 입니다.

 

문제 해석과 풀이 다 함께 살펴보시죠.

 

알고리즘

---

백준 BAEKJOON 11279

백준 11279번 최대 힙 문제 보러가기

 

반응형

 

문제 해석

 

우선 최대 힙이라는 자료구조에 대한 개념에 대해서 알고 넘어가봅시다.

최대 힙 설명 - 출처 https://velog.io/@yyj8771

위 블로그 글을 보면 감사하게도 자세하게 설명을 해주셨다.

최대 힙을 이해하셨다면 이제 파이썬으로 구현을 해봅시다.

힌트 : heapq 라는 라이브러리에 대해서 아시나요?

 

풀이

 

# 11279 최대 힙

import sys
import heapq

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

for _ in range(n):
    m = int(sys.stdin.readline())
    
    if m == 0:
        if len(heap) == 0:
            print(0)
        else:
            print((-1)*heapq.heappop(heap))
    else:
        heapq.heappush(heap, (-1)*m)

 

풀이 해석 및 팁

 

최대 힙을 간단히 설명하자면 2진 트리 모양을 가진 트리에서 루트에 가장 큰 수가 존재하고 그 아래 자식 노드로는

왼쪽이 더 큰 숫자가 존재하는 트리로 구성되어있습니다.

하지만 우리가 사용한 heapq는 이것과 반대로 루트에 가장 작은 수가 존재하고 그 아래 자식 노드로는 왼쪽이

더 작은 숫자가 존재하는 최소 힙을 구현해놓은 라이브러리입니다.

따라서 우리가 이를 문제에 적용시켜서 사용하려면 입력값을 모두 음수로 전환시켜서 출력할 때만 다시 양수로

출력해주면 최소 힙 라이브러리를 최대 힙 문제를 푸는데 사용할 수 있게되는 것 입니다.

heapq의 사용법은 단순히 값을 추가하는 heapqpush와 루트 노드를 제거하는 heapqpop이 있습니다.

문제에 나온 조건들과 코드를 잘 살펴보면 사용법을 쉽게 이해할 수 있습니다.

---

여기까지 백준 11279번 최대 힙 문제 풀이였습니다.

이번 문제의 정답률은 47% 정도입니다.

 

궁금하신 점은 댓글로 남겨주시기 바랍니다.

 

감사합니다.