[백준] 1927. 최소 힙 & 11279. 최대 힙

문제

백준 1927 최소 힙 https://www.acmicpc.net/problem/1927
백준 11279 최대 힙 https://www.acmicpc.net/problem/11279
 

최소 힙 처음 코드 (시간초과)

배열에서 min()을 이용하여 최소값을 찾았다.

n = int(input())
x = []
for _ in range(n):
    num = int(input())

    if num == 0:
        if x:
            print(min(x))
            x.remove(min(x))
        else:
            print(0)
    else:
        x.append(num)

 

최소 힙 코드

import sys
import heapq

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

for _ in range(n):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, num)
    else:
        try:
            print(heapq.heappop(heap))
        except:
            print(0)

 

최소 힙 풀이

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

입력받을 숫자의 개수인 n을 입력받고
힙 자료구조가 될 배열을 하나 만든다.
 

for _ in range(n):
    num = int(sys.stdin.readline())

n번만큼 num 숫자를 입력 받는다.
num은 최대 10만번 까지 입력될 수 있기 때문에 input()보다 빠른 sys.stdin.readline()으로 입력받는다.
 

if num != 0:
    heapq.heappush(heap, num)
else:
    try:
        print(heapq.heappop(heap))
    except:
        print(0)

만약 num이 자연수라면
힙에 자연수 num을 추가한다.
 
num이 0 이라면
힙에서 제일 작은 숫자를 꺼내서 출력하고 그 숫자를 힙에서 삭제한다.
힙에 숫자가 없고 비어있는 상태라면 0을 출력한다.

입력 조건에 음수는 입력되지 않는다 하였으니 음수일 경우를 고려한 코드는 적지 않았다.
 

최대 힙 코드

import sys
import heapq

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

for _ in range(n):
    num = int(sys.stdin.readline())
    if num != 0:
        heapq.heappush(heap, -num)
    else:
        try:
            print(-heapq.heappop(heap))
        except:
            print(0)

 

최대 힙 풀이

heapq 모듈에서는 최대 힙을 제공하지 않기 때문에 부호를 변경하여 최대힙을 직접 구현해야한다.

if num != 0:
    heapq.heappush(heap, -num)
else:
    try:
        print(-heapq.heappop(heap))
    except:
        print(0)

부호를 바꿔서 최소 힙에 넣어주고 
꺼낼때도 부호를 바꿔서 꺼내면
최대 힙과 동일한 기능을 한다.
 

새롭게 배운점 / 느낀점

• 힙큐 모듈에서 최대힙을 제공하지 않는다는 점을 알게 되었다.
  • 그래서 최대힙을 직접 구현해야 하는데 부호만 바꾸면 간단하게 최대힙도 구현 할 수 있다는걸 알게 되었다.
• 힙은 여러 값 중에서 최대값 또는 최소값을 빠르게 찾을 수 있다는걸 알게 되었다.
  • 배열은 최대 / 최소값을 찾을때 시간 복잡도가 O(N) 이지만
  • 힙은 최대 / 최소값을 찾을때 시간 복잡도가 O(logN) 이다.