자료구조 | 삭제되는 요소 |
---|---|
Stack | 가장 최근에 들어온 데이터 |
Queue | 가장 먼저 들어온 데이터 |
Priority Queue(heap) | 가장 우선순위가 높은 데이터 |
import heapq
# 원소를 추가하여 heap 자료형으로 만든다
heap = []
heapq.heappush(heap, 1)
heapq.heappush(heap, 2)
heapq.heappush(heap, 3)
heapq.heappush(heap, 4)
heapq.heappush(heap, 5)
print(heap)
#
[1, 2, 3, 4, 5]
# 이미 리스트가 있는 경우
heap_2 = [5,6,9,3,5,1]
heapq.heapify(heap_2)
print(heap_2)
#
[1, 3, 5, 6, 5, 9]
# 가장 작은 요소가 삭제된다
heapq.heappop(heap_2)
print(heap_2)
heapq.heappop(heap_2)
print(heap_2)
#
[1, 3, 5, 6, 5, 9]
[3, 5, 5, 6, 9]
[5, 5, 9, 6]
import heapq
# 튜플의 첫 번째 인자는 우선순위, 그러나 - 형태를 띄고 있기 떄문에
heap_items = [1,3,5,7,9]
max_heap = []
for item in heap_items:
heapq.heappush(max_heap, (-item, item))
print(max_heap)
# heappop 사용시 가장 작은 요소를 리턴해야 한다. 하지만 우선순위를 반대로 했기 때문에 가장 큰 수가 리턴이 되는 것을 확인 가능하다.
max_item = heapq.heappop(max_heap)
print(max_item)
# (-9, 9)
max_item = heapq.heappop(max_heap)[1]
print(max_item)
# 9
N개의 비커에 액체가 담겨 있다. 모든 비커에 있는 액체의 양이 T 이상이 될 때까지 액체가 가장 적게 담긴 두 비커의 액체를 합쳐가려 한다. 각각의 비커에 담겨있는 액체의 양을 표기한 리스트 L과 기준 T가 주어질 때, 모든 비커의 양이 T 이상이 될 때까지 필요한 작업 횟수를 리턴하는 함수를 구현해보자. (구현할 수 없는 경우 -1을 리턴)
import heapq
def my_heap_example(L, T):
""" 주어진 비커의 리스트를 힙 구조로 변환 """
heapq.heapify(L)
result = 0
while len(L) >= 2 : #IndexError 방지
""" 힙에서 최솟값을 가져옴 """
min_ = heapq.heappop(L)
if min_ >= T: # 액체의 최솟값이 T보다 크다는 조건 만족(종료)
print("-"*40, "\nresult:", result)
return result
else: # 두 번째로 작은 값 가져와서 합친 값을 힙에 삽입
min_2 = heapq.heappop(L)
heapq.heappush(L, min_ + min_2)
result += 1
print("step{}: [{},{}] 합칩".format(result, min_ , min_2))
print(" →", L)
if L[0] > T:
print("-"*40, "\nresult:", result)
return result
else:
print("-"*40, "\nMission Failed")
return -1
#
step1: [1,2] 합칩
→ [2, 3, 6, 4, 5, 7, 9, 8]
step2: [2,3] 합칩
→ [4, 5, 5, 8, 9, 7, 6]
----------------------------------------
result: 2
2
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while len(scoville) >= 1:
min_scoville_1 = heapq.heappop(scoville)
if min_scoville_1 >= K:
return answer
else:
min_scoville_2 = heapq.heappop(scoville)
heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
answer += 1
return answer
import heapq
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while scoville[0] <= K: <- 이 부분 수정
min_scoville_1 = heapq.heappop(scoville)
if min_scoville_1 >= K:
return answer
else:
min_scoville_2 = heapq.heappop(scoville)
heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
answer += 1
return answer
heapq를 사용하게 되면 heapify를 통해 heap 생성하게 되는데 이 때 sort를 하게 되면 heapify와 같아서 sort만 해도 됩니다
결정적으로 시간이 오래걸리는게 while 조건으로 min(scoville)이더라구요.
최솟값을 찾기 위해 배열 전체를 탐색해야 하니 그런 것 같습니다.
heappush를 하게 되면 알아서 최솟값이 배열 제일 앞으로 오게 되니 scoville[0]만 해도 됩니다.
(파이썬 내장 heapq는 최소힙이어서 최솟값이 제일 앞으로 오게 됩니다)
듣고 고쳤는데 효율성 테스트 다시 실패. 무엇이 문제일까?
문제에 "모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다." 이 조건도 고려해야돼요
def solution(scoville, K):
answer = 0
heapq.heapify(scoville)
while len(scoville) >= 2:
min_scoville_1 = heapq.heappop(scoville)
if min_scoville_1 >= K:
return answer
else:
min_scoville_2 = heapq.heappop(scoville)
heapq.heappush(scoville, (min_scoville_1 + min_scoville_2 * 2))
answer += 1
if scoville[0] < K:
return -1
return answer
while len(scoville) >= 2:
부분 때문에 실패한 것이라고 생각됩니다. 왜냐하면 가장 작은 값과 그 값보다 덜 작은 값이 성립이 되려면 리스트 안에는 최소 2개의 값이 있어야 하는데 그 경우에서 에러가 난 것 같습니다(확실하진 않습니다). 또한 if scoville[0] < K:\ return -1
이 부분도 추가를 하였습니다. 문제에 이미 모든 음식의 스코빌 지수를 K 이상으로 만들 수 없는 경우에는 -1을 return 합니다
라는 조건이 있었는데 이를 무시하고 문제를 푸려고 해서 에러가 났던 것 같습니다.https://gmlwjd9405.github.io/2018/05/10/data-structure-heap.html : 힙의 개념에 대해 참고하였습니다.
https://hocheon.tistory.com/70 : 힙의 개념에 대해 참고하였습니다.
https://littlefoxdiary.tistory.com/3 : 힙의 개념, 예제 등을 참고했습니다.