#1927. 최소 힙
백준의 실버2티어 문제이다. 스터디에서 했던 힙 유형을 복습하기 위해 풀게 되었다.
참고로#11279. 최대 힙과 아주 유사하다.
📖Problems
널리 잘 알려진 자료구조 중 최소 힙이 있다. 최소 힙을 이용하여 다음과 같은 연산을 지원하는 프로그램을 작성하시오.
- 배열에 자연수 x를 넣는다.
- 배열에서 가장 작은 값을 출력하고, 그 값을 배열에서 제거한다.
프로그램은 처음에 비어있는 배열에서 시작하게 된다.
입력
첫째 줄에 연산의 개수 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 연산에 대한 정보를 나타내는 정수 x가 주어진다. 만약 x가 자연수라면 배열에 x라는 값을 넣는(추가하는) 연산이고, x가 0이라면 배열에서 가장 작은 값을 출력하고 그 값을 배열에서 제거하는 경우이다. x는 231보다 작은 자연수 또는 0이고, 음의 정수는 입력으로 주어지지 않는다.
출력
입력에서 0이 주어진 횟수만큼 답을 출력한다. 만약 배열이 비어 있는 경우인데 가장 작은 값을 출력하라고 한 경우에는 0을 출력하면 된다.
예제 입력 1
1
2
3
4
5
6
7
8
9
10
11
9
0
12345678
1
2
0
0
0
0
32
예제 출력 1
1
2
3
4
5
0
1
2
12345678
0
🔍Institution
priority queue를 사용하면 된다. 이는 python에서 heapq모듈을 통해 구현한다.
또한 이 문제는 #11279. 최대 힙 문제와 유사하다는 것을 미리 알린다.
🔍Concepts
파이썬으로 힙 자료구조
참고자료 : https://www.daleseo.com/python-heapq/, https://redcrow.tistory.com/487
Heap
stack: LIFO(Last In First Out)queue: FIFO(First In First Out)- 하지만 쌓을 때부터 순서를 고려해야 하는 경우가 존재한다.
Stack과Queue가 넣은 순서대로 꺼낸다면,Priority Queue는 우선순위가 존재해서 우선순위가 높은 데이터부터 꺼내도록 구현된 자료구조이다. Heap은Priority Queue와 같이 우선 순위가 존재하는 자료구조이다.Heap: 최대값과 최소값을 빠르게 찾기 위해 만들어진 완전이진트리- Max Heap , Min Heap
Heap을 사용하는 이유
- 배열에서 최대 최소 값을 찾으려면 O(n) 이 걸리는데 비해 Heap은 O(log n)으로 성능이 더 좋다.
- 배열에서 데이터의 최대, 최소 값을 찾기 위해 사용한다
파이썬에서 Heap 기능 사용하기
module import
1
import heapq
최소 힙 생성
1
heap = []
힙에 원소 추가 :
heappush(list, item)1 2 3 4 5 6 7 8 9
from heapq import heappush heappush(heap, 4) heappush(heap, 1) heappush(heap, 7) heappush(heap, 3) print(heap) # 결과 : [1,3, 7, 4] # 시간복잡도 : O(log(n))
힙에서 원소 삭제 :
heappop(list)1 2 3 4 5 6 7 8
from heapq import heappop print(heappop(heap)) print(heap) ''' 1 [3, 4, 7] '''
기존리스트를 힙으로 변환 : 이미 원소가 들어 있는 경우 → heapify()
1 2 3 4 5 6
from heapq import heapify heap = [4, 1, 7, 3, 8, 5] heapify(heap) print(heap) # 결과 :[1, 3, 5, 4, 8, 7]
예시
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
import heapq
heap = []
# heap에 추가 : heapq.heappush(list, element)
heapq.heappush(heap, 2)
heapq.heappush(heap, 4)
heapq.heappush(heap, 5)
heapq.heappush(heap, 3)
heapq.heappush(heap, 1)
print(heap)
# >> [1, 2, 5, 4, 3]
heap2 = [2, 6, 9, 4, 7, 1]
heapq.heapify(heap2)
print(heap2)
# >> [1, 4, 2, 6, 7, 9]
while heap:
print(heapq.heappop(heap))
print(heap)
# heappop을 사용하면 가장 작은 값을 가져오고, heap은 하나씩 준다.
# 1 [2, 3, 5, 4] -> 2 [3, 4, 5] -> 3 [4, 5], 4 [5] -> 5 []
🔍Approach
🚩My submission
조건
- 0 : 배열에서 가장 작은 값 출력하고 그 값을 배열에서 제거 (
heappop()) - 다른 숫자 : 배열에 push (
heappush())
🚩Flow
- 연산 개수
n을 입력받는다.heap리스트를 만든 후heapify시킨다. - 정수
num을 입력받는다. - 만약
num이 0일 경우에는heappop()을 수행한다.- 또한 이 과정에서
heap이 비어 있을 경우에는 0을 출력하도록 한다.
- 또한 이 과정에서
num이 0이 아닐 경우(0을 제외한 수)일 경우,heap에 push한다.- for문을 n만큼 반복한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
import heapq
import sys
n = int(sys.stdin.readline()) #시간초과 방지
heap = []
for _ in range(n):
num = int(sys.stdin.readline())
n -= 1
if num == 0:
if len(heap) == 0:
print(0)
continue
print(heapq.heappop(heap))
else:
heapq.heappush(heap, num)
🚩Others submission
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
import heapq
numbers = int(input())
heap = []
#Max Heap
for _ in range(numbers):
num = int(sys.stdin.readline())
if num != 0:
heapq.heappush(heap, num)
else:
try:
print(heapq.heappop(heap))
except:
print(0)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
import sys
import heapq
input() = sys.stdin.readline()
N = int(input())
heap = []
for _ in range(N):
x = int(input())
if x == 0:
if not heap:
print(0)
else:
print(heapq.heappop(heap)
else:
heapq.heappush(heap, x)
💡TIL
- 스터디에서 ‘힙’ 부분의 진도를 나갔기 때문에 복습하기 위해 해당 문제를 풀었다.
- heap에 대해 복습하면서, 이전 최소 힙에서 heap이란 어떤 것인지 어떻게 활용하면 좋은지 알게 되었다.
- heap : 우선 순위가 존재하는 자료구조, 최대최소 문제 풀 때 활용된다.
heapq를 import하여 사용하며, 아래 코드를 사용하면 된다.
1 2 3 4 5 6
import heapq # 힙에 원소 추가 heappush(list, item) # 힙에 heappop(list) heapify()