🧷 1927번 최소 힙
(문제 링크: https://www.acmicpc.net/problem/19941)
🌸 문제
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
- 배열에 자연수 x를 넣는다.
- 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
🌸 입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 2^31보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
🌸 출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
🌸 풀이
우선 이 문제를 풀기 전에, heapq 모듈 사용하는 방법을 꼭 공부하자!
import heapq
import sys
input = sys.stdin.readline
heap = []
N = int(input())
for _ in range(N):
op = int(input())
if op == 0:
if not heap: # 힙이 비어있다면 0 출력
print(0)
else:
print(heapq.heappop(heap)) # 힙에서 가장 작은 값을 출력하고 제거
else: # 연산이 0이 아닌 경우 (정수 x를 추가하는 연산)
# 힙에 정수 x를 추가
heapq.heappush(heap, op)⌛ 시간복잡도
코드를 보면, 먼저 입력으로 주어지는 연산의 개수를 입력 받고, 그 개수만큼 연산을 반복한다. 각 연산에 대해 연산의 종류를 확인하여 0이면 힙에서 가장 작은 값을 출력하고 제거하고, 0이 아니면 해당 값을 최소 힙에 추가한다.
이 코드의 시간 복잡도는 각 연산마다 힙에 원소를 추가하거나 제거할 때 O(log N)의 시간이 걸리기 때문에 총 N번의 연산을 수행할 때 O(N log N)의 시간이 소요됨
📕 힙 자료구조(heapq 모듈)
참고 자료: https://www.daleseo.com/python-heapq/#google_vignette
힙(Heap)은 이진 트리의 일종으로, 부모 노드가 자식 노드보다 항상 크거나 작은 값을 가지는 자료구조이다. 힙은 주로 우선순위 큐(Priority Queue)를 구현하는 데 사용되며, 특히 최대 힙(Max Heap)과 최소 힙(Min Heap)이 있다.
- 부모 노드와 자식 노드 간의 관계: 부모 노드는 항상 자식 노드보다 크거나 작은 값을 갖는다. 최대 힙의 경우 부모 노드가 항상 자식 노드보다 크고, 최소 힙의 경우 부모 노드가 항상 자식 노드보다 작다.
- 완전 이진 트리(Complete Binary Tree) 구조: 힙은 완전 이진 트리의 형태를 가지며, 각 레벨에서 왼쪽부터 노드가 차례로 채워진다.
힙은 주로 우선순위 큐를 구현하는 데에 사용되고, 정렬되지 않은 리스트에서 가장 큰 값 또는 가장 작은 값에 접근할 때 유용하게 사용할 수 있다.
코드에서 사용된 heapq 모듈은 파이썬 라이브러리에 포함되어있다. 이 모듈을 사용하여 최소 힙을 간단하게 구현할 수 있음. heapq.heappush() 함수를 사용하여 원소를 추가하고, heapq.heappop()함수를 사용하여 최소 값을 제거하고 반환할 수 있다!
