최소힙

최소힙

최소힙 자료를 이용하여 다음과 같은 연산을 하는 프로그램 작성

1) 자연수가 입력되면 최소힙에 입력

2) 숫자 0 이 입력되면 최소힙에서 최솟값을 꺼내어 출력 (출력할 자료가 없으면 -1 출력)

3) -1이 입력되면 프로그램 종료

 

▣ 입력예제

5

3

6

0

5

0

2

4

0

-1

 

▣ 출력예제 

3

5

2

---

내가 쓴 코드

import sys
import heapq as hq
sys.stdin = open("input.txt",'rt')

heap = []
#-1이 입력으로 들어올 때까지 반복
while True:
    #입력받기
    num = int(input())
    #-1 들어오면 멈추고 프로그램 종료
    if num == -1:
        break
    #0 들어오면 최솟값 꺼내어 출력
    elif num == 0:
        #힙에 최솟값 있으면 꺼내서 출력
        if heap:
            print(hq.heappop(heap))
        #없으면 -1 출력
        else:
            print(-1)
    #자연수 입력되면 최소힙에 넣기
    else:
        hq.heappush(heap, num)

 

모범답안

#모범답안
import sys
import heapq as hq
sys.stdin = open("input.txt",'rt')
a = []

while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if len(a) == 0:
            print(-1)
        else:
            print(hq.heappop(a))
    else:
        hq.heappush(a,n)

 

느낀점

1. 이 문제는 그냥 힙 모듈 사용하는 느낌의 문제

2. import heapq 하고 (최소힙)
넣을 때는 heapq.heappush(힙변수,넣을것)
최솟값 뺄 때는 heapq.heappop(힙변수)

 

---

 

다시 써보기

#다시 써보자
import sys
import heapq
sys.stdin = open("input.txt",'rt')

heap = []
while True:
    n = int(input())
    if n == -1:
        break
    if n == 0:
        if heap:
            print(heapq.heappop(heap))
        else:
            print(-1)
    else:
        heapq.heappush(heap,n)