백준 1927번 최소, 최대 힙
문제
https://www.acmicpc.net/problem/1927
1927번: 최소 힙
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0
www.acmicpc.net
나의 코드
from heapq import heappop, heappush
import sys
min_heap = []
result = []
for i in range(int(input())):
inputNumber = int(sys.stdin.readline().rstrip())
if inputNumber == 0:
if len(min_heap) == 0:
result.append(0)
else:
result.append(heappop(min_heap))
else:
heappush(min_heap,inputNumber)
for i in result:
print(i)
다른 사람의 풀이
내가 if len(min_heap) ==0 이라고 사용했던 조건을 if not min_heap이라고 사용하였다. 정수는 0이 false이고 배열은 빈 배열을 false로 인식한다는 것을 알아두어야겠다.
최소 힙을 사용해 푸는 문제였다.
최소 힙이라는 개념을 몰라 공부하고 풀어야 했다.
https://transfer-kk.tistory.com/71
힙 트리 ( 최소 힙, 최대 힙 )
힙트리(heap)란? 최댓값 또는 최솟값을 빠르게 찾기 위해 고안된 완전 이진트리의 일종으로 우선순위 큐를 위해 만들어진 자료구조이다. 부모-자식 노드 간의 대소 관계가 성립하며 반정렬 상태(
transfer-kk.tistory.com
python에서는 최소 힙을 heapq 라는 내장 모듈을 사용하여 쉽게 구성할 수 있다.
heapq 모듈은 파이썬의 보통 리스트를 최소 힙처럼 다룰 수 있도록 도와주며, 빈 리스트를 생성하고 heapq 모듈의 함수를 호출할 때마다 리스트를 인자로 넘기므로서 사용할 수 있다.
힙에 원소를 추가할 때는 heappush() 함수를 이용하여 힙에 원소를 추가할 수 있다 (heappush(리스트, 넣을 값))
O(logn)의 시간 복잡도를 가진다.
힙에 원소를 삭제할 때는 heappop() 함수를 이용하여 힙에서 원소를 삭제할 수 있다. (heappop(리스트))
원소를 삭제할 대상 리스트를 인자로 넘기면, 가장 작은 원소를 삭제 후에 그 값을 리턴한다.
똑같이 O(logn)의 시간 복잡도를 가진다.
기존 리스트를 힙으로 변환하고 싶을 때는 heapq 모듈의 heapify()라는 함수를 사용하면 된다. (heapify(리스트))
O(n)의 시간 복잡도를 지닌다.
heapq 모듈을 사용해 최대 힙을 구하고 싶다면 힙에 튜플(tuple)를 원소로 추가하거나 삭제하면, 튜플 내에서 맨 앞에 있는 값을 기준으로 최소 힙이 구성되는 원리를 이용한다. 따라서, 최대 힙을 만들려면 각 값에 대한 우선 순위를 구한 후, (우선 순위, 값) 구조의 튜플(tuple)을 힙에 추가하거나 삭제한다. 그리고 힙에서 값을 읽어올 때는 각 튜플에서 index 1에 있는 값을 취하면 된다.
ex)
heappush(heap, (-num, num)) #(우선 순위, 값)
heappop(heap)[1]
heapq 모듈의 nsmallest() 함수와 nlargest() 함수를 사용하여주어진 리스트에서 가장 작은/큰 n개의 값을 담은 리스트를 반환할 수 있다.그 결과 리스트의 마지막 값이 n번째 작은/큰 값이 된다.ex) nsmallest(2,[5,6,8,4,2,1])[-1]
참고한 사이트