반응형
풀이
최소힙과 최대힙을 각각 만들어서 값을 넣어줬다. Insert 작업이 들어오면 각각의 힙에 값을 넣어줬고 Delete 작업이 들어오면 각각의 힙에서 값을 pop해줬다.
마지막에 두 힙에 값이 남아있다면 answer 배열에 최댓값과 최솟값을 찾아서 넣어줬다.
코드
import heapq
def solution(operations):
answer = [0, 0]
minHeap = [] # 최소힙
maxHeap = [] # 최대힙
for operation in operations:
if operation[0] == 'I': # Insert일 경우 두 힙에 값 push
num = int(operation[2:])
heapq.heappush(minHeap, num)
heapq.heappush(maxHeap, -num)
elif len(maxHeap) == 0: # delete 작업 전에 힙에 값이 없으면 continue
continue
elif operation == 'D 1': # delete일 경우 두 힙에서 값 pop
heapq.heappop(maxHeap)
minHeap.pop()
elif operation == 'D -1':
heapq.heappop(minHeap)
maxHeap.pop()
# 두 힙에 값이 남아있다면 최댓값과 최솟값을 넣어준다.
if maxHeap and minHeap:
answer[0], answer[1] = -maxHeap[0], minHeap[0]
return answer
반응형
'Algorithm > Programmers' 카테고리의 다른 글
[고득점 Kit(정렬)] H-Index (Python) (0) | 2022.02.08 |
---|---|
[고득점 Kit(정렬)] 가장 큰 수 (Swift, Python) (0) | 2022.02.03 |
[고득점 Kit(힙)] 디스크 컨트롤러 (Swift, Python) (0) | 2022.01.28 |
[고득점 Kit(힙)] 더 맵게 (Python) (0) | 2022.01.27 |
[고득점 Kit(해시)] 베스트앨범 (Swift, Python) (0) | 2022.01.26 |
댓글