[백준] 1927번 : 최소 힙

유형 : 힙, 자료구조

 

[예제 입력]

9
0
12345678
1
2
0
0
0
0
32

[예제 출력]

0
1
2
12345678
0

---

1. 내 풀이

1) 첫 번째 풀이

import sys

n = int(sys.stdin.readline())

list = []
for i in range(n):
    x = int(sys.stdin.readline())

    if x == 0: # 가장 작은 값 출력
        if len(list) == 0:
            print(0)
        else:
            print(min(list))
            list.remove(min(list)) # min 제거

    else:
        list.append(x)

▷ 시간초과가 발생하길래, sys.stdin.readline()을 이용하였다.
▷ heapq라는 라이브러리를 몰라서 못 썼는데, 내가 알고 있던... 얄팍한 지식으로는 안 되는 듯 하다.

 

 

2) 두 번째 풀이

import sys
import heapq

n = int(sys.stdin.readline())

list = []
for i in range(n):
    x = int(sys.stdin.readline())

    if x == 0: # 가장 작은 값 출력
        if len(list) == 0:
            print(0)
        else:
            print(heapq.heappop(list))

    else:
        heapq.heappush(list, x)

▷ 풀이 영상과 구글에 다른 풀이를 검색해봤더니 다들 heapq 라이브러리를 사용하길래 heapq을 이용한 풀이로 수정했다.

▷ heapq 모듈은 이진 트리 기반의 최소 힙 자료구조를 제공한다고 한다.

▷ heappop() 함수는 리스트를 인자로 넘기게 되면, 가장 작은 원소를 삭제하고 그 값을 리턴한다.

▷ heappush() 함수는 힙에 원소를 추가할 수 있다.

 

** 자세한 설명은 다음 사이트를 참고하길 추천한다.

https://www.daleseo.com/python-heapq/

[파이썬] heapq 모듈 사용법

 

 

2. 풀이

출처 : 패스트캠퍼스 - 알고리즘 / 기술면접 완전 정복 올인원 패지지 Online

 

** 핵심 아이디어 **
1. 최소 힙의 기본적인 기능을 구현

 

import heapq

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

for _ in range(n):
    data = int(input())
    
    if data == 0:
    	if heap:
            result.append(heapq.heapop(heap))
        else:
            resut.append(0)
            
    else:
       heapq.heappush(heap, data)
        
for data in result:
	print(data)

 

 

문제 출처 : https://www.acmicpc.net/problem/1927

1927번: 최소 힙