백준 11279번: 최대 힙
✔ 풀이를 위한 아이디어
- 우선순위 큐 (Priority Queue)와 힙 (Heap)
✔ 수정 전 코드 [시간 초과]
import sys
N = int(sys.stdin.readline())
Heap = [-1]
for _ in range(N):
x = int(sys.stdin.readline())
if x == 0:
if len(Heap) == 1:
print("0")
else:
Heap[1], Heap[len(Heap) - 1] = Heap[len(Heap) - 1], Heap[1]
print(Heap.pop())
i = 1
while True:
if 2*i < len(Heap)-1:
if Heap[i] < Heap[2*i]:
Heap[i], Heap[2*i] = Heap[2*i], Heap[i]
i = 2*i
elif 2*i+1 < len(Heap)-1:
if Heap[i] < Heap[2*i+1]:
Heap[i], Heap[2*i+1] = Heap[2*i+1], Heap[i]
i = 2*i+1
else:
break
else:
Heap.append(x)
i = len(Heap) - 1
while i > 1:
if Heap[i] > Heap[i//2]:
Heap[i], Heap[i//2] = Heap[i//2], Heap[i]
i = i//2
else:
break
- 약 1년도 더 전에 (벌써 1년이나 됐어?!) 자료구조 수업 시간에 배웠던 힙 (Heap). 까먹어서 다시 공부하였다. https://chanhuiseok.github.io/posts/ds-4/
- 직접 힙 (Heap) 을 구현해보았지만 백준은 야박하게도 시간 초과를 때려버렸다. 시간 초과 문제를 해결할 방법을 알아보던 중, 파이썬에서 heapq라는 모듈을 지원한다는 것을 알게 되었고, 바로 해당 모듈을 활용하는 쪽으로 코드를 수정하였다.
- 나중에 코딩 고수가 되면 위의 코드를 수정하여서 시간초과가 안나게 해보고 싶다.
✔ 수정 후 코드
import sys
import heapq
N = int(sys.stdin.readline())
Heap = []
for _ in range(N):
x = int(sys.stdin.readline())
if x == 0:
if len(Heap) == 0:
print("0")
else:
tmp = heapq.heappop(Heap)
print(tmp[1])
else:
heapq.heappush(Heap, (-x, x))
- 파이썬에서 지원하는 heapq 모듈을 공부하였다. https://www.daleseo.com/python-heapq/
- 기본적으로 지원하는 heapq 모듈은 최소 힙을 지원하고 있기 때문에, (-x, x)와 같이 튜플 (tuple) 에 넣어서 역순으로 정렬되도록 하고, 출력 할 때는 index 1의 원래 값만 나타나도록 했다.
- 처음 제출했을 때는 Heap의 크기를 고려하지 않고 2 x i 나 2 x i + 1 같은 값을 참조했다가 indexError가 났었다.
- 이후 Python3와 PyPy3에서 모두 시간초과를 맛보고, heapq 모듈을 사용하는 쪽으로 넘어갔다.
✔ 관련 개념
- 힙 (Heap)과 heapq 모듈의 활용
Author And Source
이 문제에 관하여(백준 11279번: 최대 힙), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@dlehdtjq00/백준-11279번-최대-힙저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)